#include <queue>
#include <utility>
#include <iostream>

#define X first
#define Y second
#define A 5005
int cb[A][A];
int d[3] = {-1,0,1};

using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  queue<pair<int, int>> qu;
  int n, q, x, y;
  cin >> n >> q;
  for (int i=0; i<n;i++){
    cin >> x >> y;
    qu.push({x,y});
    cb[x][y]=1;
  }

  while (qu.size()) {
    auto q = qu.front(); qu.pop();
    int x=q.X, y=q.Y;
    int di = cb[x][y]+1;
    for (int i=0; i<3;i++) for (int j=0; j<3;j++) {
      if (x+d[i] < 0) continue;
      if (y+d[j] < 0) continue;
      if (x+d[i] > 5000) continue;
      if (y+d[j] > 5000) continue;

      if (cb[x+d[i]][y+d[j]] == 0) {
        cb[x+d[i]][y+d[j]] = di;
        qu.push({x+d[i],y+d[j]});
      }
    }

  }


  for (int i=0; i<q;i++) {
    cin >> x >> y;
    cout << cb[x][y]-1 << '\n';
  }



  return 0;
}