진료 예약 배정과 휴진

문제

어느 병원은 1일부터 D일까지의 진료일을 운영한다. d일에는 최대 c_d명까지 예약을 받을 수 있고, c_d가 0이면 그날은 처음부터 예약이 불가능하다. 병원 접수 시스템에는 Q개의 요청이 순서대로 들어온다. 요청은 두 종류이다. 첫째, 1 l r 요청은 환자 한 명이 l일 이상 r일 이하의 날 중 하루를 희망한다는 뜻이다. 이 구간에서 아직 남은 자리가 있는 날 중 가장 이른 날에 환자를 예약하고 그 날짜를 답한다. 예약하면 그날의 남은 자리가 1 줄어든다. 구간 안에 남은 자리가 있는 날이 없으면 예약하지 못하고 -1을 답한다. 둘째, 2 l r 요청은 병원이 l일부터 r일까지 임시 휴진을 선언한다는 뜻이다. 이 구간에서 아직 남은 자리가 있던 모든 날의 남은 자리를 0으로 만들고, 그렇게 닫힌 날의 개수를 답한다. 이미 자리가 0이던 날은 세지 않는다. 한 번 자리가 0이 된 날은 다시 열리지 않는다. 모든 요청에 대한 답을 순서대로 출력한다.

입력

첫 줄에 D와 Q가 공백으로 주어진다 (1 ≤ D ≤ 20,000, 1 ≤ Q ≤ 20,000). 둘째 줄에 c_1, ..., c_D 가 공백으로 주어진다 (0 ≤ c_d ≤ 10^9). 이어서 Q개의 줄에 요청이 하나씩 t l r 형태로 주어진다. t는 1 또는 2이고 1 ≤ l ≤ r ≤ D 이다. 모든 값은 정수이다.

출력

요청마다 답을 한 줄에 하나씩 Q줄 출력한다.

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

1
2
2
-1
2
-1

1 3
2
1 1 1
2 1 1
1 1 1

1
1
-1

출처: Devin.KR 자체 제작