#include <bits/stdc++.h> using namespace std; typedef long long LL; inline double read_double(){ char ch = getchar(); int f = 1; double x = 0; while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } if (ch == '.') { double d = 0.1; ch = getchar(); while (ch >= '0' && ch <= '9') { x += d * (ch - '0'), d *= 0.1; ch = getchar(); } } return (f == -1 ? -x : x); } const int N = 3e5 + 9; struct node { double s, x, y; int id; node(double ss = 0, double xx = 0, double yy = 0, int idd = 0) : s(ss), x(xx), y(yy), id(idd) {} } a[N]; bool operator < (const node &x, const node &y) { if (x.x != y.x) return x.x < y.x; else if (x.s != y.s) return x.s < y.s; else if (x.y != y.y) return x.y < y.y; else return x.id < y.id; } double area(double x, double y, double x1, double y1, double x2, double y2) { return 0.5L * (x + y - x1 - y1) * (x2 - y2 - x + y); } set<node> peak; int n, q; double insert(double s, double x) { while (1) { auto it = peak.lower_bound(node(s, x, 0, -1)); if (fabsl(it->x - x) <= 1e-8) { double _x = it->x, _y = it->y; double x1 = (--it)->x, y1 = (it++)->y; double x2 = (++it)->x, y2 = (it--)->y; s += area(_x, _y, x1, y1, x2, y2); peak.erase(it), it = peak.lower_bound(node(s, x, 0, -1)); } double x2 = it->x, y2 = it->y, x1 = (--it)->x, y1 = it->y; double d1 = x - x1 + y1, d2 = x2 + y2 - x, d = min(d1, d2); if (area(x, d, x1, y1, x2, y2) >= s) { double s1 = x - x1 - y1, s2 = x2 - y2 - x; return 0.5L * (sqrtl((s1 - s2) * (s1 - s2) + 8.0 * s) - s1 - s2); } if (d1 <= d2) { double x0 = (--it)->x, y0 = it->y; s += area(x1, y1, x0, y0, x2, y2); peak.erase(++it); } else { it++; double x3 = (++it)->x, y3 = it->y; s += area(x2, y2, x1, y1, x3, y3); peak.erase(--it); } } } double top(double x) { auto it = peak.lower_bound(node(0, x, 0, 0)); if (fabsl(x - it->x) <= 1e-8) return it->y; double x2 = it->x, y2 = it->y, x1 = (--it)->x, y1 = it->y; return max(y1 - (x - x1), y2 - (x2 - x)); } namespace query { int lb(int x) {return x & -x;} struct BIT { int Mn, C[N << 1]; void init(int siz) { Mn = siz; for (int i = 1; i <= Mn; i++) C[i] = n + 1; } void upd(int x, int v) { x = Mn - x + 1; while (x <= Mn) { C[x] = min(C[x], v), x += lb(x); } } int qry(int x) { x = Mn - x + 1; int res = n + 1; while (x) { res = min(res, C[x]), x -= lb(x); } return res; } } T; struct ques { double x, y; int id; } qu[N]; double inx[N << 2], iny[N << 2]; int tpx = 0, tpy = 0, ans[N]; struct Node { int x, y, id; } A[N], Qu[N]; bool cmp(Node x, Node y) { if (x.y != y.y) return x.y > y.y; else return x.x < y.x; } map<double, int> mp; int Main() { for (int i = 1; i <= q; i++) { qu[i].x = read_double(), qu[i].y = read_double(); qu[i].id = i, qu[i].y = top(qu[i].x) - qu[i].y; double _x = qu[i].x + qu[i].y, _y = qu[i].y - qu[i].x; qu[i].x = _x, qu[i].y = _y; inx[++tpx] = _x, iny[++tpy] = _y; } for (int i = 1; i <= n + 2; i++) { double _x = a[i].x + a[i].y, _y = a[i].y - a[i].x; a[i].x = _x, a[i].y = _y; inx[++tpx] = _x, iny[++tpy] = _y; } sort(inx + 1, inx + tpx + 1), sort(iny + 1, iny + tpy + 1); tpx = unique(inx + 1, inx + tpx + 1) - inx - 1; tpy = unique(iny + 1, iny + tpy + 1) - iny - 1; for (int i = 1; i <= tpx; i++) mp[inx[i]] = i; for (int i = 1; i <= n + 2; i++) A[i].x = mp[a[i].x], A[i].id = a[i].id; for (int i = 1; i <= q; i++) Qu[i].x = mp[qu[i].x], Qu[i].id = i; A[n + 1].id = A[n + 2].id = 0, mp.clear(); for (int i = 1; i <= tpy; i++) mp[iny[i]] = i; for (int i = 1; i <= n + 2; i++) A[i].y = mp[a[i].y]; for (int i = 1; i <= q; i++) Qu[i].y = mp[qu[i].y]; sort(Qu + 1, Qu + q + 1, cmp), sort(A + 1, A + n + 3, cmp); T.init(tpx); int lst = 1; for (int i = 1; i <= q; i++) { while (lst <= n + 2 && A[lst].y >= Qu[i].y) T.upd(A[lst].x, A[lst].id), lst++; ans[Qu[i].id] = T.qry(Qu[i].x); } for (int i = 1; i <= q; i++) printf("%d\n", ans[i]); return 0; } } int main() { scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) { a[i].s = read_double(), a[i].x = read_double(), a[i].id = i; } a[n + 1] = node(0, -1e9, 1e9, 0), a[n + 2] = node(0, 1e9, 1e9, 0); peak.insert(a[n + 1]), peak.insert(a[n + 2]); for (int i = 1; i <= n; i++) { a[i].y = insert(a[i].s, a[i].x); peak.insert(node(a[i].s, a[i].x, a[i].y, i)); } query::Main(); return 0; }