#include<iostream>
#include<queue>

using namespace std;

int n, kv;
int dist[5555][5555];
bool was[5555][5555];

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

struct s
{
  int x, y, d;
};

queue<s> q;

int main(int argc, char const *argv[]) {
  cin>>n>>kv;
  int x, y;
  for(int i = 0; i < n; i++)
  {
    cin>>x>>y;
    q.push({x, y, 0});
    was[x][y] = true;
  }
  while(!q.empty())
  {
    s c = q.front();
    q.pop();
    dist[c.x][c.y] = c.d;
    for(int i = 0; i < 8; i++)
    {
      if(c.x+dx[i] >= 0 && c.x+dx[i] <= 5000 && c.y+dy[i] >= 0 && c.y+dy[i] <= 5000 && !was[c.x+dx[i]][c.y+dy[i]])
      {
        was[c.x+dx[i]][c.y+dy[i]] = true;
        q.push({c.x+dx[i], c.y+dy[i], c.d+1});
      }
    }
  }
  for(int i = 0; i < kv; i++)
  {
    cin>>x>>y;
    cout<<dist[x][y]<<" ";
  }
  cout<<endl;
  return 0;
}