#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=double;
using pll=pair<ll,ll>;
using vll=vector<ll>;
using vpll=vector<pll>;
using vvll=vector<vll>;
#define FOR(i,a,b) for(ll i=a;i<(ll)b;++i)
#define ROF(i,a,b) for(ll i=a;i>=(ll)b;--i)
#define F(n) FOR(i,0,n)
#define FF(n) FOR(j,0,n)
#define aa first
#define bb second
#define pb push_back

#define MX 5007

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

struct N {
  ll x,y,i,d;
};

bool vis[MX][MX];
int rt[MX][MX];
bool ok(ll x, ll y) {
  return x>=0 && y>=0 && x<MX && y<MX;
}

int main(){
  ios::sync_with_stdio(0);
  int n,q; cin >> n >> q;
  set<ll> G;
  queue<N> Q;
  F(n) { // guards
    ll x,y; cin >> x >> y;
    Q.push({x,y,i,0ll});
  }
  while(Q.size()) {
    auto cur=Q.front(); Q.pop();
    if(vis[cur.x][cur.y])continue;
    vis[cur.x][cur.y]=1;
    rt[cur.x][cur.y]=cur.d;
    F(8) {
      N nx = {cur.x+dx[i],cur.y+dy[i],cur.i,cur.d+1};
      if(ok(nx.x,nx.y) && !vis[nx.x][nx.y]) {
        Q.push(nx);
      }
    }
  }
  F(q) {
    ll x,y; cin >> x >> y;
    cout << rt[x][y]<<endl;
  }
  return 0;
}