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

using namespace std;

#define ABS(X) (x < 0 ? -x : x)

int dist(pair<int,int> x, pair<int,int> y){
  auto z = make_pair(abs(x.first - y.first), abs(x.second - y.second));
  auto m = min(z.first, z.second);
  return m + (z.first - m) + (z.second - m);
}

int binSearch(vector<pair<int,int>> guards, pair<int,int> incident){
  //printf("search for closest to %d %d\n", incident.first, incident.second);
  for(int i= 0; i < guards.size(); i++){
    if(guards[i].first > incident.first){
      //printf("foudn %d %d, bigger, idx %d\n", guards[i].first, guards[i].second, i);
      if(i > 0){
        return min(dist(guards[i], incident), dist(guards[i-1],incident));
      }
      return dist(guards[i], incident);
    }
  }
  return dist(guards[guards.size()-1], incident);
}

int main(){
  //ios::sync_with_stdin(false);

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

  vector<pair<int, int>> guardsY(0);
  vector<pair<int, int>> guardsX(0);
  for(int i = 0; i < N; i++){
    cin >> x >> y;
    guardsX.push_back(make_pair(x,y));
    guardsY.push_back(make_pair(y,x));
  }

  sort(guardsX.begin(), guardsX.end());
  sort(guardsY.begin(), guardsY.end());

  vector<vector <pair <int,int> > > closestX(5001);
  int idx = 0;
  int gidx = 0;
  closestX[0].push_back(guardsX[gidx++]);
  for(int i = 1; i < guardsX.size(); i++){
    if(guardsX[i].first == guardsX[0].first) closestX[0].push_back(guardsX[i]);
    else break;
  }
  for(int i = 1; i < 5001; i++){
    if(gidx < guardsX.size() && guardsX[gidx].first - i > i - closestX[i-1][0].first){
      // just copy
      for(auto g : closestX[i-1])
        closestX[i].push_back(g);
    } else if(gidx < guardsX.size() && guardsX[gidx].first - i == i - closestX[i-1][0].first){
      // marge both
      for(auto g : closestX[i-1])
        closestX[i].push_back(g);
      while(gidx < guardsX.size() && guardsX[gidx].first - i == i - closestX[i-1][0].first){
        closestX[i].push_back(guardsX[gidx]);
        if(i < 5001) closestX[i+1].push_back(guardsX[gidx]);
        gidx++;
      }
      i++;
    } else {
      if(gidx < guardsX.size() && guardsX[gidx].first - i < i - closestX[i-1][0].first){
        while(gidx < guardsX.size() && guardsX[gidx].first - i < i - closestX[i-1][0].first){
          closestX[i].push_back(guardsX[gidx]);
          gidx++;
        }
      } else {
        // just copy
        for(auto g : closestX[i-1])
          closestX[i].push_back(g);
      }
    }
  }

  vector<vector<pair<int,int>>> closestY(5001);
  idx = 0;
  gidx = 0;
  closestY[0].push_back(guardsY[gidx++]);
  for(int i = 1; i < guardsY.size(); i++){
    if(guardsY[i].first == guardsY[0].first) closestY[0].push_back(guardsY[i]);
    else break;
  }
  for(int i = 1; i < 5001; i++){
    if(gidx < guardsY.size() && guardsY[gidx].first - i > i - closestY[i-1][0].first){
      // just copy
      for(auto g : closestY[i-1])
        closestY[i].push_back(g);
    } else if(gidx < guardsY.size() && guardsY[gidx].first - i == i - closestY[i-1][0].first){
      // marge both
      for(auto g : closestY[i-1])
        closestY[i].push_back(g);
      while(gidx < guardsY.size() && guardsY[gidx].first - i == i - closestY[i-1][0].first){
        closestY[i].push_back(guardsY[gidx]);
        if(i < 5001) closestY[i+1].push_back(guardsY[gidx]);
        gidx++;
      }
      i++;
    } else {
      if(gidx < guardsY.size() && guardsY[gidx].first - i < i - closestY[i-1][0].first){
        while(gidx < guardsY.size() && guardsY[gidx].first - i < i - closestY[i-1][0].first){
          closestY[i].push_back(guardsY[gidx]);
          gidx++;
        }
        continue;
      }
      // just copy
      for(auto g : closestY[i-1])
        closestY[i].push_back(g);
    }
  }

  for(int i = 0; i < Q; i++){
    cin >> x >> y;
    auto best = min(binSearch(closestX[x], make_pair(x,y)), binSearch(closestY[y], make_pair(y,x)));
    cout << best << endl;
  }


  return 0;
}