题目描述

译自 POI 2011 Round 3. Day 2. A「Meteors」

Byteotian 星际联盟（Byteotian Interstellar Union，BIU） 最近在附近的星系发现了一颗新的行星。尽管这颗行星由于奥妙重重的流星雨不适合人类居住，但是这给我们带来了一个非常有趣的研究对象。
BIU 的 $ n $ 个成员国为了采集这些陨石的样本，将它们的空间站发射到了这颗行星的轨道附近。BIU 将这颗星球的轨道分为 $ m $ 份（编号从 $ 1 $ 到 $ m $，且第 $ m $ 份和第 $ 1 $ 份相邻），第 $ i $ 份上部署了第 $ O_i $ 个国家的太空站。
BIU 已经准确地预测了接下来 $ k $ 场陨石雨的情况。BIU 的第 $ i $ 个成员国希望能够收集 $ P_i $ 单位的陨石样本。你的任务是判断对于每个国家，在第几次陨石雨之后，才能收集足够的陨石。

输入格式

输入的第一行包含两个整数，$ n, m $，表示 BIU 的成员国数量和轨道被划分的区域数量。
第二行包含 $ m $ 个整数，第 $ i $ 个数 $O_i$ 表示第 $ i $ 段轨道上有第 $ O_i $ 个国家的太空站。
第三行包含 $ n $ 个整数，第 $ i $ 个数 $P_i$ 表示第 $ i $ 个国家希望收集的陨石数量。
第四行包含一个整数 $ K $，表示 BIU 预测了接下来的 $ K $ 场陨石雨。
接下来的 $ k $ 行，第 $ i $ 行包含三个整数 $ L_i, R_i, A_i $，表示第 $ k $ 场陨石雨的发生地点在从 $ L_i $ 顺时针到 $ R_i $ 的区间中（如果 $ L_i \le R_i $，就是 $ Li, L{i+1}, \ldots , R_i $，否则就是 $ Li, L{i+1}, \ldots , m-1, m, 1, \ldots , R_i $），向区间中的每个太空站提供 $ A_i $ 单位的陨石样本。

输出格式

输出包含 $ n $ 行。第 $ i $ 行的数 $ W_i $ 表示第 $ i $ 个国家在第 $ W_i $ 场陨石雨之后能够收集到足够的陨石样本。如果到第 $ k $ 场流星雨结束后仍然收集不到目标数量 $ P_i $，输出 NIE（波兰语中的 No）。

样例

input

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

output

3
NIE
1

数据范围与提示

对于 $ 25\% $ 的测试数据，$ n, m, k \le 1000 $。
对于 $ 100\% $ 的测试数据，$ 1 \le n, m, k \le 3 \times 10^5 $，$ 1 \le O_i \le n $，$ 1 \le P_i, A_i \le 10^9 $。