#include <stdio.h>
#include <stdlib.h>
#pragma GCC optimize ("O3")

int max(int a, int b){
	if (a < b)
		return b;
	return a;
}
int abs(int n){
	if (n < 0)
		return -n;
	return n;
}

int main (void){
	int hl_n, inc_n;
	scanf("%d %d", &hl_n, &inc_n);
	
	int hl_x[hl_n];
	int hl_y[hl_n];
	int inc_x[inc_n];
	int inc_y[inc_n];
	
	for (int i = 0; i < hl_n; i++){
		scanf("%d %d", &hl_x[i], &hl_y[i]);
	}
	
	for (int i = 0; i < inc_n; i++){
		scanf("%d %d", &inc_x[i], &inc_y[i]);
	}

	for (int i = 0; i < inc_n; i++){
		int min = 999999999, min_step;
		for (int j = 0; j < hl_n; j++){
			min_step = max(abs(hl_x[j] - inc_x[i]), abs(hl_y[j] - inc_y[i]));
			if (min_step < min){
				min = min_step;
				if (min_step == 0)
					break;
			}
		}
		printf("%d\n", min);
	}
	
	return 0;
}