#include <stdio.h>

int abs(int x){
    return x < 0 ? -x : x;
}

int max(int a, int b){
    return a > b ? a : b;
}

int main(){
    int N, Q;
    scanf("%d %d", &N, &Q);
    int X[N], Y[N];
    int iX[Q], iY[Q];
    for(int i = 0; i < N; i++){
        scanf("%d %d", &X[i], &Y[i]);
    }
    for(int i = 0; i < Q; i++){
        scanf("%d %d", &iX[i], &iY[i]);
    }

    for(int i = 0; i < Q; i++){
        int x = iX[i];
        int y = iY[i];

        int yDiff = abs(Y[0] - y);
        int xDiff = abs(X[0] - x);
        int best_dist = max(yDiff, xDiff);

        for(int j = 1; j < N; j++){
            yDiff = abs(Y[j] - y);
            xDiff = abs(X[j] - x);
            int current_dist = max(yDiff, xDiff);
            if(current_dist < best_dist){
                best_dist = current_dist;
            }
        }

        printf("%d\n", best_dist);
    }
    return 0;
}