#include <bits/stdc++.h>
using namespace std;

const int X = 5002;

int dp[X][X];

int query(int x1, int y1, int x2, int y2)
{
	x1--; y1--;
	x1 = max(x1, 0);
	y1 = max(y1, 0);
	x2 = min(x2, X - 1);
	y2 = min(y2, X - 1);
	return dp[x2][y2] - dp[x1][y2] - dp[x2][y1] + dp[x1][y1];
}

int main()
{
	int n, q;
	scanf("%d %d", &n, &q);
	while(n--)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		x++; y++;
		dp[x][y]++;
	}
	for(int i = 1; i < X; i++)
		for(int j = 1; j < X; j++)
			dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
	while(q--)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		x++; y++;
		int a = 0, b = X, c;
		while(a < b)
		{
			c = (a + b) / 2;
			if(query(x - c, y - c, x + c, y + c))
				b = c;
			else a = c + 1;
		}
		printf("%d\n", a);
	}
}