#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
map<int, vector<int>> guardsT; //y,x_rows

int x, y;

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

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

for (auto &row:guardsT) {
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 itX=guards.lower_bound( x);
if (itX == guards.end()) --itX;
auto up = itX;
auto down = itX;

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

// find initial y (min dist)
auto itY=guardsT.lower_bound( y);
if (itY == guards.end()) --itY;
auto left = itY;
auto right = itY;

if (left == guardsT.begin()) {
left = guardsT.end();
} else --left;


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

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


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

if (left != guardsT.end() && right != guardsT.end()) {
   if ( distance1d(y, left->first) < distance1d(y, right->first))
   {
     itY = left;
     if (left == guardsT.begin()) {
       left = guardsT.end();
     } else --left;
   }
   else 
   {
     itY = right;
     right++;
   }
} else if (left != guardsT.end()) {
     itY = left;
     if (left == guardsT.begin()) {
       left = guardsT.end();
     } else --left;
} else if (right != guardsT.end()) {
     itY = right;
     right++;
}
else break;

if ( md<=distance1d(y, itY->first)) break;


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

}

cout << md << endl;
}



return 0;
}