시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 512 MB 0 0 0 0.000%

문제

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 Vi liters of water from the Ri-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 Di and Ci each - diameter and capacity of the i-th reservoir.

Next Q lines contain two integers Ri and Vi each.

출력

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

제한

  • 2 ≤ N ≤ 105
  • 1 ≤ Q ≤ 2·105
  • 1 ≤ Ci ≤ 1000
  • 1 ≤ Di, Vi ≤ 109
  • 1 ≤ Ri ≤ N

예제 입력 1

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

예제 출력 1

5
0
5
4
2

힌트

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.