题目描述

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≤R_i$，就是 $L_i,L_i+1,…,R_i$，否则就是 $L_i,L_i+1,…,M−1,M,1,…,R_i$），向区间中的每个太空站提供$A_i$单位的陨石样本。

输出格式

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

如果到第$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

数据范围

• $1≤n,m,k≤3×10^5$
• $1≤P_i≤10^9$
• $1≤A_i<10^9$

来源

• 算法竞赛进阶指南