求调玄关

#include<bits/stdc++.h>
using namespace std;
int n, q;
const int maxn = 1e5 + 10;
long long d[maxn];
int c[maxn];
long long rmax[maxn][20], g[maxn][20];
int f[maxn][20];
void initr() {
	for(int i = 1; i <= n; i++)
		rmax[i][0] = d[i];
	for(int j = 1; (1 << j) <= n; j++)
		for(int i = 1; i <= n - (1 << j) + 1; i++)
			rmax[i][j] = max(rmax[i][j - 1], rmax[i + (1 << (j - 1))][j - 1]);
}
int querymax(int a, int b) {
	int len = b - a + 1;
	long long ans = 0;
	for(int i = 0, j = a; (1 << i) <= len; i++) {
		if((len >> i) & 1) {
			ans = max(ans, rmax[j][i]);
			j += (1 << i);
		}
	}
	return ans;
}
void initf() {
	for(int i = 1; i < n; i++) {
		int l = i + 1, r = n + 1;
		while(l < r) {
			int mid = (l + r) / 2;
			if(querymax(i + 1, mid) <= d[i])
				l = mid + 1;
			else
				r = mid;
		}
		f[i][0] = l;
		g[i][0] = c[f[i][0]];
	}
	f[n][0] = n + 1;
	g[n][0] = c[f[n][0]];
	for(int j = 1; j <= 16; j++) {
		for(int i = 1; i <= n; i++) {
			f[i][j] = f[f[i][j - 1]][j - 1];
			g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1];
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; i++)
		cin >> d[i] >> c[i];
	initr();
	c[n + 1] = INT_MAX;
	initf();
	while(q--) {
		int r, v;
		cin >> r >> v;
		if(v <= c[r]) {
			cout << r << "\n";
			continue;
		}
		v -= c[r];
		for(int t = 16; t >= 0; t--) {
			if(v > g[r][t]) {
				r = f[r][t];
				v -= g[r][t];
			}
		}
		r = f[r][0];
		if(r == n + 1)
			r = 0;
		cout << r << "\n";
	}
}