Background

Description

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

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

BIU 的第 i个成员国希望能够收集 pi单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。

Format

Input

第一行是两个数N,M。 第二行有M个数，第i个数Oi表示第i段轨道上有第Oi个国家的太空站。 第三行有N个数，第i个数Pi表示第i个国家希望收集的陨石数量。 第四行有一个数K，表示BIU预测了接下来的K场陨石雨。 接下来K行，每行有三个数Li,Ri,Ai，表示第K场陨石雨的发生地点在从Li顺时针到Ri的区间中（如果Li<=Ri，就是Li,Li+1,...,Ri，否则就是Ri,Ri+1,...,m-1,m,1,...,Li），向区间中的每个太空站提供Ai单位的陨石样本。

Output

N行。第i行的数Wi表示第i个国家在第Wi波陨石雨之后能够收集到足够的陨石样本。如果到第K波结束后仍然收集不到，输出NIE。

Samples

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

3
NIE
1

Limitation

1<=n,m,k<=3*10^5 1<=Pi<=10^9 1<=Ai<10^9