분수
시간 제한1.5초메모리 제한512 MB
물이 넘치면 아래쪽에서 지름이 더 큰 가장 가까운 저수지로 흘러갈 때, R번 저수지에 V리터를 부으면 흐름이 어디서 끝나는지 각 질의에 답한다.
문제
새로 만든 분수는 아래 그림처럼 위에서 아래로 1부터 정수 번호가 붙은 N개의 원형 물 저장고가 수직으로 정렬되어 있다.
각 저장고에는 지름, 용량, 그리고 저장고 안의 물을 원하는 만큼 흘려보낼 수 있는 수도꼭지가 있다. 물의 양이 저장고 용량을 넘으면 넘친 물은 옆면 밖으로 흘러나와, 지름이 엄격히 더 큰 저장고 중 가장 가까운 곳으로 내려간다. 그런 저장고가 없으면 물길로 내려간다.
Ri번 저장고의 수도꼭지에서 Vi리터의 물을 흘려보냈을 때 흐름이 끝나는 저장고의 번호를 묻는 Q개의 독립적인 질의에 답해야 한다. 흐름이 물길에서 끝나면 답은 0이다.
입력
첫째 줄에 두 정수 N과 Q가 주어진다.
다음 N개 줄에 각각 두 정수 Di와 Ci가 주어진다. i번 저장고의 지름과 용량이다.
다음 Q개 줄에 각각 두 정수 Ri와 Vi가 주어진다.
출력
Q개 줄에 질의가 주어진 순서대로 답을 한 줄에 하나씩 출력한다.
제한
- 2 ≤ N ≤ 10^5
- 1 ≤ Q ≤ 2·10^5
- 1 ≤ Ci ≤ 1000
- 1 ≤ Di, Vi ≤ 10^9
- 1 ≤ Ri ≤ N
힌트
처음 두 질의는 위 그림에 나와 있다.
질의들은 서로 독립적이므로, 세 번째 질의에서 다섯 번째 저장고는 넘치지 않는다.