가장 가까운 빈 진료일

문제

병원 예약 시스템에는 1일부터 D일까지의 진료일이 있고, d일에는 최대 c_d명까지 예약을 받을 수 있다. c_d가 0인 날은 휴진일이다. 환자 N명이 입력 순서대로 예약을 요청한다. i번째 환자는 희망일 t_i와 허용 범위 w_i를 말하며, 1 이상 D 이하이면서 t_i - w_i 이상 t_i + w_i 이하인 날 중에서 아직 정원이 차지 않은 날만 배정받을 수 있다. 시스템은 그런 날 중 희망일과의 차이 |d - t_i|가 가장 작은 날을 배정하고, 차이가 같은 날이 두 개이면 더 이른 날을 배정한다. 배정되면 그 날의 남은 정원이 1 줄어든다. 조건을 만족하는 날이 하나도 없으면 그 환자의 예약은 거절되며 이후의 상태는 변하지 않는다. 각 환자에 대해 배정된 날짜를 출력하되, 거절되면 0을 출력하시오.

입력

첫 줄에 D와 N이 주어진다. (1 ≤ D ≤ 200,000, 1 ≤ N ≤ 200,000) 둘째 줄에 c_1, c_2, ..., c_D가 공백으로 구분되어 주어진다. (0 ≤ c_d ≤ 10^9) 이어서 N개의 줄에 각각 t_i와 w_i가 주어진다. (1 ≤ t_i ≤ D, 0 ≤ w_i ≤ D)

출력

N개의 줄에 i번째 환자가 배정받은 날짜를 출력한다. 거절되었다면 0을 출력한다.

5 6
1 2 0 1 1
3 1
3 0
2 1
2 2
1 3
5 1

2
0
2
1
4
5

1 3
2
1 0
1 5
1 0

1
1
0

출처: Devin.KR 자체 제작