1919 . 王老先生
TopCoder
Description
俗話說的好：「王老先生有塊地 yee呀yee呀喲」
雖然說王老先生有塊地，但他並不想種田，所以他僱用了$n$個人管理他的$m$塊農地(排成一列)，編號1到$m$。雖然一個農地一定恰為一個人管理，但一個人可以管理很多農地，所以這些人也僱用了一些手下在他所管理的農地工作。
王老先生是個非常在乎工作效率的人，所以他給了$n$個人定了目標$V_1, V_2, \dots, V_n$，代表第$i$個人需要賺到$V_i$元。
王老先生也非常在乎他所僱用的人是否有在認真工作，所以他買了一台機器人，用來追蹤$n$個人的手下工作的情況。這台機器人每次會用照相機拍下某個區間$[L_j, R_j]$的情況以確保大家有在認真工作。對於第$i$個人，如果他有某個手下在區間$[L_j, R_j]$認真工作(也就是說他有一塊在區間$[L_j, R_j]$的農地)，那麼他會賺到$C_j$元。然而，如果某個人有兩個以上的手下在區間內，那麼他還是只會賺到$C_j$元。
假設所有人都認真工作，那麼第$i$個人在第幾張照片後就達成目標(或無法達成目標)呢?
Input Format
第一行有三個正整數$1\leq n,m,Q\leq 10^ 5$，分別代表王老先生僱用的人，有的農地數以及機器人拍照的次數。第二行有$m$個正整數$1\leq a_1, a_2, \dots, a_m\leq n$，代表農地的主人是誰。第三行有$n$個正整數$1\leq V_1, V_2, \dots, V_n\leq 10^ 9$，代表$n$個人的目標。之後的$Q$行，每行有三個正整數$1\leq L_j\leq R_j\leq m ,1\leq C_j\leq 10^ 9$，代表機器人拍了$[L_j, R_j]$這個區間，且這次被拍到的人會賺到$C_j$元。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $L_j = R_j$ | 8 |
| 2 (5~9) | $m, Q\leq 10^ 4$ | 13 |
| 3 (10~14) | $a_i$相異 | 37 |
| 4(0~19) | 無 | 42 |
Output Format
請輸出$n$行。第$i$行輸出一個正整數$t$，代表第$i$個人在恰在拍第$t$次照後達到目標。若$Q$次以後還是無法達成目標，請輸出-1。
Sample Input 1
1 2 3 2 1
5 10 15 20
1 5 3
1 4 3
2 4 9
Sample Output 1
3
3
-1
Hints
第一次照相後所有人賺到的錢：
3, 3, 3, 0
第二次照相後所有人賺到的錢：
6, 6, 6, 0
第三次照相後所有人賺到的錢：
6, 15, 15, 0
Problem Source
Problem set / Description by Paupière
建國中學105學年度校內第五次模擬賽pE
題目取自2015 TOI第一階段選訓第二次模擬考pB
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 8 |
| 2 | 5~9 | 13 |
| 3 | 10~14 | 37 |
| 4 | 0~19 | 42 |