题目描述

Byteotian Interstellar Union (BIU) 有 $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$，表示第 $i$ 场陨石雨的发生地点在从 $L_i$ 顺时针到 $R_i$ 的区间中（如果 $L_i \le R_i$，就是 $L_i, L_i+1, \dots, R_i$，否则就是 $L_i, L_i+1, \dots, M-1, M, 1, \dots, R_i$），向区间中的每个太空站提供 $A_i$ 单位的陨石样本。

输出格式

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

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

样例解释

初始状态

• 成员国数量 $N = 3$
• 轨道段数 $M = 5$
• 太空站分布：$[1, 3, 2, 1, 3]$（轨道 1 有国家 1 的太空站，轨道 2 有国家 3 的太空站，轨道 3 有国家 2 的太空站，轨道 4 有国家 1 的太空站，轨道 5 有国家 3 的太空站）
• 各国需求：$[10, 5, 7]$
• 陨石雨场数 $K = 3$

陨石雨详情

第 1 场陨石雨：$L = 4, R = 2, A = 4$
由于 $L = 4 > R = 2$，区间为 $[4, 5, 1, 2]$（顺时针）。

• 轨道 4：国家 1 获得 $4$
• 轨道 5：国家 3 获得 $4$
• 轨道 1：国家 1 获得 $4$
• 轨道 2：国家 3 获得 $4$

当前累计：

• 国家 1：$4 + 4 = 8$
• 国家 2：$0$
• 国家 3：$4 + 4 = 8$

第 2 场陨石雨：$L = 1, R = 3, A = 1$
区间 $[1, 2, 3]$：

• 轨道 1：国家 1 获得 $1$（累计 $9$）
• 轨道 2：国家 3 获得 $1$（累计 $9$）
• 轨道 3：国家 2 获得 $1$（累计 $1$）

第 3 场陨石雨：$L = 3, R = 5, A = 2$
区间 $[3, 4, 5]$：

• 轨道 3：国家 2 获得 $2$（累计 $3$）
• 轨道 4：国家 1 获得 $2$（累计 $11$，满足需求）
• 轨道 5：国家 3 获得 $2$（累计 $11$，满足需求）

各国满足需求时间

• 国家 1：在第 3 场后满足（$11 \ge 10$）
• 国家 2：最终累计 $3 < 5$，输出 NIE
• 国家 3：在第 3 场后满足（$11 \ge 7$）

注意：国家 3 实际上在第 3 场后才满足，虽然第 2 场后已有 $9 \ge 7$，但题目要求"在第几次陨石雨之后"，即累计达到目标的最早场次。

数据范围

• $1 \le N, M, K \le 3 \times 10^5$
• $1 \le P_i \le 10^9$
• $1 \le A_i < 10^9$

时间与空间要求

时间限制：建议在 $O((N + M + K) \log N \log K)$ 或更优复杂度内完成。

空间限制：建议在 $O(N + M + K)$ 空间内完成。