#2169. 「POI2011 R3 Day2」流星 Meteors

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ceba_robot

题目描述

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

Byteotian 星际联盟(Byteotian Interstellar Union,BIU) 最近在附近的星系发现了一颗新的行星。尽管这颗行星由于奥妙重重的流星雨不适合人类居住,但是这给我们带来了一个非常有趣的研究对象。
BIU 的 n 个成员国为了采集这些陨石的样本,将它们的空间站发射到了这颗行星的轨道附近。BIU 将这颗星球的轨道分为 m 份(编号从 1 m ,且第 m 份和第 1 份相邻),第 i 份上部署了第 A_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 ,就是 L_i, L_{i+1}, \ldots , R_i ,否则就是 R_i, R_{i+1}, \ldots , m-1, m, 1, \ldots , L_i ),向区间中的每个太空站提供 A_i 单位的陨石样本。

输出格式

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

样例

样例输入

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

样例输出

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