[IOI Camp Judge]農田分配 (題目備份)

IOI Camp Judge是暫時性的，因此在這裡作個題目備份，請大家參考～
題解在這裡

農田分配

Time Limit: 8s

Description

米提爾是個大地主，擁有 M 塊農地，這些農地由左而右排成一直線，我們依序將這些農地由左至右編號為 1,2,…,M。

米提爾擁有 N 個助手來幫助他管理他的農地，每塊農地都會有恰好一個助手管理。米提爾對他的助手非常友善，因此他建立了一個加薪機制，每個助手有著自己的積分，一開始大家的積分都是 0，只要積分達到某個標準，助手便可以加薪。基於米提爾對每個助手的喜愛感不盡相同，每個助手所要達到的標準也不一定相同。

但米提爾該如何設計累積積分的方法呢？聰明的他設計了一台機器人，機器人每次會對一個區間 [Li,Ri] 的農地進行拍一張照片，一共拍攝 Q 張，米提爾在得到這些照片後，會一一看過，並根據照片給予一些助手積分，對於第 i 張照片，米提爾會給予出現在這張照片農地的管理者都增加 Vi 的積分，如果某個助手在裡面出現了多次，那個助手並不會因此多得到積分，仍然是得到 Vi 的積分。

身為有加薪機會的助手，當然很好奇自己到底能不能加到薪，現在他們都想問你，在米提爾看到哪一張照片時可以達到自己的積分標準。

Input Format

第一行有一個正整數 T，代表總共有幾筆測試資料。

每筆測試資料第一行有兩個以空白隔開的正整數 N 與 M，表示有 N 個助手與 M 塊農地。

第二行有 N 個正整數 Gi，第 i 個數字為第 i 個助手的積分標準。

第三行有 M 個正整數 Fi，第 i 個數字為管理第 i 塊農地的助手，我們並不保證每個助手都會有管理的農地。

第四行有一個正整數 Q，表示米提爾設計的機器人照了 Q 張照片。

接著有 Q 行，每行三個正整數 Li,Ri,Vi，表示第 i 張照片所照到的農地範圍，以及管理這些農地的助手分別可獲得 Vi 的積分。

• 1≤T≤100
• 1≤N,M,Q≤100000
• 1≤Gi,Vi≤109
• 1≤Fi≤N
• 1≤Li≤Ri≤M
• 對於所有測試資料，我們保證不超過 6 筆測試資料滿足 N+M+Q>3000

Output Format

對於每筆測試資料，請輸出 N 個整數於一行，第 i 個數字表示第 i 個助手可以在哪一張照片時達到他的標準，若無法達到標準請輸出 −1。

Sample Input

1
3 5
10 12 5
1 2 2 3 1
3
1 4 5
2 5 3
2 4 4

Sample Output

-1 3 1

Hint

• 在第一張照片時，三個助手的積分依序為 5,5,5。
• 在第二張照片時，三個助手的積分依序為 8,8,8。
• 在第三張照片時，三個助手的積分依序為 8,12,12。