#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());

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


  return 0;
}