34757번 - 제설 작업

문제

ZOAC 대회 전날 밤, 폭설로 도로가 하얗게 뒤덮였다. 대회 참가자들이 제시간에 도착할 수 있도록 운영진은 새벽부터 제설 작업에 나섰고, 진행 상황을 수시로 총괄 관리자에게 보고하기로 했다.

도로는 1ドル$번부터 $N$번까지의 구간으로 나누어져 있고, 각 $i$번 구간에는 눈이 $S_i$만큼 쌓여 있다.

제설 작업은 총 $M$개이며, 작업 번호가 작은 순서대로 진행된다. 작업 $t(1\le t\le M)$는 지정된 구간 $[L_t,R_t]$에 최대 적재량 $C_t$인 제설차 한 대를 투입하는 일이다. 제설차는 항상 구간 번호가 증가하는 방향으로만 이동하며, 한 구간의 눈을 완전히 치우기 전에는 다음 구간으로 넘어가지 않는다. 제설차가 치운 눈의 총량이 $C_t$에 도달하거나 $[L_t,R_t]$의 제설이 모두 끝나면 그 작업은 종료된다. 단, 시간이 지남에 따라 눈이 녹거나 새로 쌓이지 않는다. 즉, 제설을 통해 눈을 치우는 경우만 고려하면 된다.

총괄 관리자는 다음과 같은 $Q$개의 쿼리를 보내고, 운영진은 각 쿼리에 대해 진행 상황을 보고한다.

• $A$ $B$ $T$: $t$번째 작업까지 수행했을 때$(1\le t\le M),ドル 구간 $[A,B]$에서 치워진 눈의 총량이 $T$ 이상이 되는 가장 작은 $t$를 보고한다. 그러한 $t$가 없으면 -1을 보고한다.

운영진을 도와, 각 쿼리에 대해 보고할 값을 출력하는 프로그램을 작성하라.

입력

첫 번째 줄에 세 정수 $N,ドル $M,ドル $Q$가 공백으로 구분되어 주어진다.$(1\le N,M,Q\le 200,円 000)$

두 번째 줄에 $N$개의 정수 $S_i$가 공백으로 구분되어 주어진다. $(1\le S_i\le 10^{12})$

세 번째 줄부터 $M$개의 줄에 걸쳐 각 작업의 정보인 세 정수 $L_t,ドル $R_t,ドル $C_t$가 공백으로 구분되어 주어진다. $(1\le L_t\le R_t\le N;$ 1ドル\le C_t\le 10^{18})$

그 다음 $Q$개의 줄에 걸쳐 세 정수 $A,ドル $B,ドル $T$가 공백으로 구분되어 한 줄에 하나씩 주어진다. $(1\le A\le B\le N;$ 1ドル\le T\le 10^{18})$

출력

각 $Q$개의 쿼리에 맞는 답을 한 줄에 하나씩 출력한다.

제한

노트

작업이 $t$번까지 끝났을 때 $i$번 구간에 남아 있는 눈의 양을 $S_i^{(t)}$로 두면, 구간 $[A,B]$에서 치워진 눈의 총량은 \[\sum_{i=A}^{B}\bigl(S_i-S_i^{(t)}\bigr)\] 이다.