#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef double ld;

typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

#define PB push_back

#define FOR(prom, a, b) for (ll prom = (a); prom < (ll)(b); ++prom)
#define F(a) FOR(i, 0, a)
#define FF(a) FOR(j, 0, a)

#define EPS (1e-10)

#define EQ(a, b) (fabs(a-b) <= fabs(a+b) * EPS)

#define MX 300000

const int D = 2; // Dimension
int N, C;
struct pt{ll x[D];}p[MX];

bool cmp(pt a, pt b)  {return a.x[C] < b.x[C];}
#define PW(A) ((A) * (A))

void ini (int l = 0, int r=N-1, int d=0){
    if (l >= r) return;
    int M  = (l + r) >> 1;
    C = d%D, nth_element(p+l, p+M, p+r+1, cmp);
    ini (l, M - 1, d + 1), ini (M + 1, r, d+1);
}

ll dis(pt x, pt y) {
    ll S = 0;
    //F(D) S+=PW(x.x[i]-y.x[i]);
    S = max(fabs(x.x[0] - y.x[0]), fabs(x.x[1] - y.x[1]));
    return S;
}

ll gt(pt x, int l = 0, int r=N-1, int d=0){
    ll t, C=d%D, M=(l+r)>>1;
    if (l>=r) return l^r?ll(2e18):dis(x, p[l]);
    if (x.x[C] < p[M].x[C]) {
        if ((t = gt(x, l, M-1, d+1))>PW(x.x[C]-p[M].x[C]))
            t=min(t, gt(x, M+1, r, d+1));
    } else if ((t=gt(x, M+1, r, d+1)) > PW(x.x[C] - p[M].x[C]))
            t=min(t, gt(x, l, M-1, d+1));
    return min (dis(x, p[M]), t);
}


int main() {
    ios::sync_with_stdio(false);

    ll n, m, x, y;
    cin >> n >> m;
    N = n;
    F(n) {
        cin >> x >> y;
        p[i].x[0] = x;
        p[i].x[1] = y;
    }

    ini(0, N - 1, 0);

    F(m) {
        cin >> x >> y;
        pt point;
        point.x[0] = x;
        point.x[1] = y;
        cout << gt(point) << endl;
    }





    return 0;
}