「Meteors」 流星

Byteotian Interstellar Union有N个成员国。

现在它发现了一颗新的星球，这颗星球的轨道被分为M份（第M份和第1份相邻），第i份上有第$A_i$个国家的太空站。

这个星球经常会下陨石雨，BIU已经预测了接下来K场陨石雨的情况。

BIU的第i个成员国希望能够收集$P_i$单位的陨石样本。

你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。

输入格式

第一行是两个数N,M。

第二行有M个数，第i个数$O_i$表示第i段轨道上有第$O_i$个国家的太空站。

第三行有N个数，第i个数$P_i$表示第i个国家希望收集的陨石数量。

第四行有一个数K，表示BIU预测了接下来的K场陨石雨。

接下来K行，每行有三个数$L_i,R_i,A_i$，表示第K场陨石雨的发生地点在从$L_i$顺时针到$R_i$的区间中（如果$L_i \le R_i$，就是$L_i,L_i+1,\dots,R_i$，否则就是$R_i,R_i+1,\dots,M-1,M,1,\dots,L_i$），向区间中的每个太空站提供$A_i$单位的陨石样本。

输出格式

输出共N行，第i行的数$W_i$表示第i个国家在第$W_i$波陨石雨之后能够收集到足够的陨石样本。

如果到第K波结束后仍然收集不到，输出NIE。

数据范围

$1 \le n,m,k \le 3\times 10^5$
$1 \le P_i \le 10^9$
$1 \le A_i < 10^9$

输入样例：

3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2

输出样例：

3
NIE
1

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解