#include <iostream>
#include <vector>

#define lad printf("%s:%d	%d\n", __func__, __LINE__, step);

using namespace std;

vector<vector<bool>> pole;


int detector(int x, int y) {
	int step = 0;

	if(pole[x][y])
		return 0;
	while(true)
	{
//lad;
		for(int xs = x - step; xs <= x + step; xs++)
		{
//lad;
			if (xs>=0 && xs<= 5000 && y-step <= 5000 && y-step >=0) {
				if(pole[xs][y-step])
				return step;
			}

			if (xs>=0 && xs<= 5000 && y + step <= 5000 && y + step >=0) {
				if(pole[xs][y+step])
					return step;
			}
			
		}

		for(int ys = y-step; ys <= y+step; ys++)
		{
//lad;
			if (ys >= 0 && ys <= 5000 && x-step <= 5000 && x-step >= 0) {
				if(pole[x-step][ys])
					return step;
			}
			if (ys >= 0 && ys <= 5000 && x + step <= 5000 && x + step >= 0) {
				if(pole[x+step][ys])
					return step;
			}
		}
		step++;
	}
}

int main() {
	int grd, inc;
	scanf("%d %d", &grd, &inc);
	
	
	for(int i = 0;i<=5000;i++)
	{
		pole.push_back(vector<bool> (5001, false));
	}


	int x, y;
	for (int i = 0 ; i < grd ; i++) {
//lad;	
	scanf("%d %d", &x, &y);
		pole[x][y] = true;
	}
	for (int i = 0 ; i < inc ; i++) {
//lad;	
	scanf("%d %d", &x, &y);
		printf("%d\n", detector(x,y));
	}
	return 0;
}