#include <bits/stdc++.h>
using namespace std;

using ii=pair<int, int>;
#define aa first
#define bb second

int dst[5012][5012];

int main() {
  int n, q; scanf("%d%d", &n, &q);
  queue<ii> bq;
  for (int i = 0; i < n; i++) {
    int sx, sy; scanf("%d%d", &sx, &sy);
    bq.push({sx, sy});
    dst[sx][sy] = 1;
  }
  while (!bq.empty()) {
    ii cur = bq.front();
    bq.pop();
    for (int x = -1; x < 2; x++) {
      for (int y = -1; y < 2; y++) {
        if (!x && !y) continue;
        int nx = cur.aa + x, ny = cur.bb + y;
        if (nx < 0 || nx > 5000 || ny < 0 || ny > 5000) continue;
        if (dst[nx][ny]) continue;
        dst[nx][ny] = dst[cur.aa][cur.bb] + 1;
        bq.push({nx, ny});
      }
    }
  }
  for (int i = 0; i < q; i++) {
    int sx, sy; scanf("%d%d", &sx, &sy);
    printf("%d\n", dst[sx][sy]-1);
  }
  return 0;
}