268. 流星

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 \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