#include <stdio.h>

int main()
{
	int n, q, i = 0, j;
	scanf("%d %d", &n, &q);
	int **guards = (int**)malloc(n * sizeof(int*));
	for(i = 0; i < n; i++)
	{
		guards[i] = (int*)malloc(2 * sizeof(int));
		scanf("%d %d", &guards[i][0], &guards[i][1]);
	}
	int **indicate = (int**)malloc(q * sizeof(int*));
	for(i = 0; i < q; i++)
	{
		indicate[i] = (int*)malloc(2 * sizeof(int));
		scanf("%d %d", &indicate[i][0], &indicate[i][1]);
	}
	int x, y, put, shortest_way = 5500;
	for(i = 0; i < q; i++)
	{
		for(j = 0; j < n; ++j)
		{
			x = indicate[i][0] - guards[j][0];
			y = indicate[i][1] - guards[j][1];
			if(x < 0)
			{
				x *= -1;
			}
			if(y < 0)
			{
				y *= -1;
			}

			put = x >= y ? x:y;
			
			if(shortest_way > put)
			{
				shortest_way = put;
			}
		}
		
		
			
		
		printf("%d\n", shortest_way);
		shortest_way = 5001; 
	}
	return 0;
}