20342번 - Fountain 서브태스크다국어

A new fountain consists of N vertically aligned circular water reservoirs numbered from top to bottom with integers starting from 1, as shown below:

Each reservoir has its diameter, capacity and a tap which can release any amount of water inside the reservoir. Whenever water volume exceeds reservoir capacity, the excess water pours out of its sides and flows down into the closest one that has a strictly larger diameter or down to waterways if no such reservoir exists.

You have to answer Q independent queries of the following kind: what is the number of the reservoir where flow ends if you release V_i liters of water from the R_i-th reservoir’s tap? If the flow ends in waterways the answer should be 0.

First line of input contains two integers - N and Q.

Next N lines contain two integers D_i and C_i each - diameter and capacity of the i-th reservoir.

Next Q lines contain two integers R_i and V_i each.

Print Q lines with one integer in each - answers to the queries in the order they are given.

• 2 ≤ N ≤ 10⁵
• 1 ≤ Q ≤ 2·10⁵
• 1 ≤ C_i ≤ 1000
• 1 ≤ D_i, V_i ≤ 10⁹
• 1 ≤ R_i ≤ N

The first two queries are illustrated on the image above.

Since the queries are independent from each other, for the third query the fifth reservoir won’t overflow.