#include <iostream>
#include <vector>

using namespace std;


struct place {
public:
	place(): x(0), y(0) {};
	place(int x, int y) : x(x), y(y) {};
	
	int x;
	int y;
};



int main(){


	cout.sync_with_stdio(false);

	int N,Q;
	int x,y;
	int min;
	cin >> N >> Q;

	vector<place> guards;
	vector<int> outputs;

	for (int i = 0; i < N; i++){
		cin >> x >> y;
		guards.push_back(place(x,y));
	}
	for (int i = 0; i < Q; i++){
		cin >> x >> y;
		min = 999999;
		for (auto & guard: guards){
				int xA = abs(x - guard.x);
				int yA = abs(y - guard.y);
			//	cout <<"x,y =="<< xA << " " << yA << endl;
				if (xA > yA) {
					if (min > xA)
						min = xA;
				}
				else { 
					if (min > yA)
						min = yA;
				}
				
		}
		outputs.push_back(min);
	}
	
	for (auto & out: outputs)
		cout << out << '\n';

	return 0;
}