题目描述

Byteotian Interstellar Union有$\red {N}$个成员国。

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

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

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

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

输入格式

第一行是两个数$\red {N,M}$。

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

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

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

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

输出格式

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

如果到第$\red {K}$波结束后仍然收集不到，输出NIE。

样例

输入样例

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

输出样例

3
NIE
1

提示

$\red {1≤n,m,k≤3\times 10^5}$

$\red {1≤P _i~ ≤10^9}$

$\red {1≤A _i~ <10^9}$