#include <stdio.h>
#include <stdlib.h>

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 power(int n){
	return n*n;
}

int main (void){
	int hl_n, inc_n;
	scanf("%d %d", &hl_n, &inc_n);
	
	int *hl_x = malloc(hl_n*sizeof(int));
	int *hl_y = malloc(hl_n*sizeof(int));
	
	int *inc_x = malloc(inc_n*sizeof(int));
	int *inc_y = malloc(inc_n*sizeof(int));
	
	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]);
	}
	
	int dist;
	for (int i = 0; i < inc_n; i++){
		int min = 999999999, min_step;
		for (int j = 0; j < hl_n; j++){
			dist = power(hl_x[j] - inc_x[i]) + power(hl_y[j] - inc_y[i]);
			if (dist < min){
				min = dist;
				min_step = max(abs(hl_x[j] - inc_x[i]), abs(hl_y[j] - inc_y[i]));
			}
		}
		printf("%d\n", min_step);
	}
	return 0;
}