Description

Everyone knows what a fountain is, right? Now there is a fountain made of $N$ disks, numbered from top to bottom as $1 \sim N$. The diameter of the $i$-th disk is $D_i$, and its capacity is $C_i$. If the amount of water in a disk exceeds its capacity, the water will overflow and flow downward, until it enters a disk whose radius is larger than the radius of this disk. If there is no disk below that satisfies this condition, the water will flow into the pool under the fountain.

Now you are given $Q$ queries. Each query is described as follows:

• Pour $V_i$ units of water into disk $R_i$, and determine which disk the water will finally flow into and stop at.

If it finally flows into the pool, output $0$.

Note that each query does not affect the others.

Input Format

The first line contains two integers $N, Q$, representing the number of disks and the number of queries.
The next $N$ lines each contain two integers $D_i, C_i$, representing a disk.
The next $Q$ lines each contain two integers $R_i, V_i$, representing a query.

Output Format

Output $Q$ lines, each containing one integer representing the answer to the query.

6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8

5
0
5
4
2

Hint

Sample 1 Explanation

The first two queries are illustrated in the figure below:

Because each query does not affect the others, for the third query, the water in disk $5$ will not overflow.

Constraints and Notes

This problem uses bundled testdata.

• Subtask 1 (30 pts): $N \le 1000$, $Q \le 2000$.
• Subtask 2 (30 pts): $D_i$ is a strictly increasing sequence.
• Subtask 3 (40 pts): No special restrictions.

For $100\%$ of the testdata:

• $2 \le N \le 10^5$.
• $1 \le Q \le 2 \times 10^5$.
• $1 \le C_i \le 1000$.
• $1 \le D_i, V_i \le 10^9$.
• $1 \le R_i \le N$.

Statement

Translated from eJOI 2020 Day1 A Fountain.

Translated by ChatGPT 5