rt,wa了11个点

#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = (j); i <= (k); i ++)
#define per(i, j, k) for(int i = (j); i >= (k); i --)
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 2e5 + 5, base = 1e5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, q;
vector<int> p[N];
struct SegT {
	int l, r, val;
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define val(x) tr[x].val
} tr[N * 50];
int rt[N], idx;
void update(int &x, int lst, int l, int r, int v) {
	x = ++ idx;
	tr[x] = tr[lst];
	val(x) ++;
	if(l == r) return;
	int mid = l + r >> 1;
	if(v <= mid) update(l(x), l(lst), l, mid, v);
	else update(r(x), r(lst), mid + 1, r, v);
}
int query(int x, int y, int l, int r, int ql, int qr) {
	if(ql <= l && r <= qr) return val(x) - val(y);
	int mid = l + r >> 1, res = 0;
	if(ql <= mid) res = query(l(x), l(y), l, mid, ql, qr);
	if(qr > mid) res += query(r(x), r(y), mid + 1, r, ql, qr);
	return res;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n;
	rep(i, 1, n) {
		int x, y;
		cin >> x >> y;
		p[x + y].push_back(x - y);
	}
	rep(i, 0, 2e5) {
		if(i != 0) rt[i] = rt[i - 1];
		for(auto po : p[i]) update(rt[i], rt[i], -base, base, po);
	}
	cin >> q;
	while(q --) {
		int a, b, k;
		cin >> a >> b >> k;
		int x = a + b, y = a - b;
		int l = 0, r = base * 4, res = 0;
		while(l <= r) {
			int mid = l + r >> 1;
			int L = max(-base, y - mid), R = min(base, y + mid);
			if(query(rt[min(base + base, x + mid)], rt[max(0, x - mid - 1)], -base, base, L, R) >= k) 
				res = mid, r = mid - 1;
			else l = mid + 1;
		}
		cout << res << '\n';
	}
	return 0;
}