#include <iostream>
#include <vector>

using namespace std;

struct guard {
int x;
int y;
};

int main() {

int n, q;
cin >> n >> q;

vector<guard> guards;
guards.reserve(n);

int x, y;

for (int i=0; i<n; ++i) {
cin >> x >> y;
guards.push_back({x,y});
}

for (int i=0; i<q; ++i) {
cin >> x >> y;

int md = 10000;
for (auto const &g:guards) {

md=min(md,max(abs(g.x-x),abs(g.y-y)));

}

cout << md << endl;
}



return 0;
}