#include <iostream>
#include <vector>
#include <algorithm>

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);
	cin.sync_with_stdio(false);

	int N,Q;
	int x,y;
	int m;
	int xA, yA;
	cin >> N >> Q;

	vector<place> guards;

	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;
		m = 999999;
		for (auto & guard: guards){
				if(m == 0) break;
				xA = abs(x - guard.x);
				yA = abs(y - guard.y);
				m  = min(m, max(xA, yA));
		}
		cout << m << '\n';
	}

		

	return 0;
}