题目描述

译自 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$，就是 $L_i, L_{i+1}, \ldots , R_i$，否则就是 $L_i, 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）。

样例

输入

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

输出

text 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$。