#include <bits/stdc++.h>
#include <bits/extc++.h>

#define maxn 500005
#define inf 1e18
#define ll long long
#define pr pair<int, int>

using namespace std;

int n, q;
struct node{
	int x, y;
}p[maxn];

ll sqr(int x) {
	return 1ll * x * x;
}

ll dis(node a, node b) {
	return sqr(a.x - b.x) + sqr(a.y - b.y);
}

int bg[maxn];
int tot;
__gnu_pbds::gp_hash_table<ll, int> xk[35];
vector<int> dk[maxn << 4];

ll t[maxn];
void add(int x, ll k) {
	for (; x; x -= x & -x) t[x] = min(t[x], k);
}
ll qry(int x) {
	ll res = inf;
	for (; x <= n; x += x & -x) res = min(res, t[x]);
	return res;
}

vector<pr> qr[maxn];
ll ans[maxn];

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++) t[i] = inf;
	for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y);
	for (int i = 1; i <= q; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		qr[y].push_back({x, i});
	}
	for (int i = 1; i <= n; i++) {
		for (int k = 1; (1ll << k) <= 2e8; k++) {
			auto &st = xk[k];
			int id = 0;
			int px = p[i].x >> k;
			int py = p[i].y >> k;
			for (int dx = px - 1; dx <= px + 1; dx++) {
				for (int dy = py - 1; dy <= py + 1; dy++) {
					if (dx < 0 || dy < 0) continue;
					if (st.find(((ll)dx * 1e9) + dy) == st.end()) continue;
					auto &t = dk[st[((ll)dx * 1e9) + dy]];
					for (int o : t) {
						add(o, dis(p[i], p[o]));
						if (dis(p[i], p[o]) < sqr(1 << (k - 1))) id = max(id, o);
					}
				}
			}
			if (!id) goto Cn;
			for (int j = bg[k] + 1; j <= id; j++) {
				auto &t = dk[st[((ll)(p[j].x >> k) * 1e9) + (p[j].y >> k)]];
				for (auto it = t.begin(); ; it++) {
					if (*it == j) {
						t.erase(it);
						break;
					}
				}
			}
			bg[k] = id;
			Cn:;
			auto &w = st[((ll)(p[i].x >> k) * 1e9) + (p[i].y >> k)];
			if (!w) w = ++tot;
			dk[w].push_back(i);
		}
		for (auto x : qr[i]) ans[x.second] = qry(x.first);
	}
	for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
	return 0;
}