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,…,R\_i$，否则就是$R\_i,R\_i+1,…,M-1,M,1,…,L\_i$），向区间中的每个太空站提供$A\_i$单位的陨石样本。

输出格式

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

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

数据范围

$1 \le n,m,k \le 3\*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 可能含有视频讲解