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

using namespace std;

int distance(int aX, int aY, int bX,int bY)
{ return max(abs(aX-bX),abs(aY-bY)); }

int distance1d(int aX, int bX)
{ return abs(aX-bX); }


int main() {

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

map<int, vector<int>> guards; //x,y_rows

int x, y;

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

for (auto &row:guards) {
sort(row.second.begin(), row.second.end());
}


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

int md = 10000;


// find initial x (min dist)
auto it=guards.lower_bound( x);
if (it == guards.end()) --it;
auto up = it;
auto down = it;

if (up == guards.begin()) {
up = guards.end();
} else --up;

while (true) {
if (up != guards.end() && down != guards.end()) {
   if ( distance1d(x, up->first) < distance1d(y, down->first))
   {
     it = up;
     if (up == guards.begin()) {
       up = guards.end();
     } else --up;
   }
   else 
   {
     it = down;
     down++;
   }
} else if (up != guards.end()) {
     it = up;
     if (up == guards.begin()) {
       up = guards.end();
     } else --up;
} else if (down != guards.end()) {
     it = down;
     down++;
}
else break;

if ( md<distance1d(x, it->first)) break;


auto yIt = lower_bound(it->second.begin(), it->second.end(), y);
if (yIt == it->second.end()) yIt--;
md = min(md, distance(x, y, it->first, *yIt));
if (yIt != it->second.begin()) yIt--;
md = min(md, distance(x, y, it->first, *yIt));

}

cout << md << endl;
}



return 0;
}