Byteotian Interstellar Union (BIU) 最近在附近的一个星系中发现了一颗新行星。由于奇异的流星雨，这颗行星不适合殖民，但另一方面，这使得它成为了一个极其有趣的研究对象。

BIU 的成员国已经在行星轨道附近放置了空间站。空间站的目标是采集飞过岩石的样本。BIU 委员会将轨道划分为 $m$ 个扇区，编号从 $1$ 到 $m$，其中扇区 $1$ 和 $m$ 相邻。每个扇区都有一个空间站，属于 $n$ 个成员国之一。

每个国家都申报了其在任务结束前打算收集的流星样本数量。你的任务是根据未来几年的流星雨预测，确定每个国家何时可以停止采集样本。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 300\,000$)，用空格分隔，分别表示 BIU 成员国的数量和轨道划分的扇区数量。

第二行包含 $m$ 个整数 $o_i$ ($1 \le o_i \le n$)，用空格分隔，表示各扇区空间站所属的国家。

第三行包含 $n$ 个整数 $p_i$ ($1 \le p_i \le 10^9$)，用空格分隔，表示各国家打算收集的流星样本数量。

第四行包含一个整数 $k$ ($1 \le k \le 300\,000$)，表示流星雨预测的数量。接下来的 $k$ 行按时间顺序给出了流星雨预测。第 $i$ 行包含三个整数 $l_i, r_i, a_i$（用空格分隔），表示预计在扇区 $l_i, l_{i+1}, \dots, r_i$（若 $l_i \le r_i$）或扇区 $l_i, l_{i+1}, \dots, m, 1, \dots, r_i$（若 $l_i > r_i$）发生流星雨，这些扇区中的每个空间站将获得 $a_i$ 个流星样本 ($1 \le a_i \le 10^9$)。

在至少占总分 $20\%$ 的测试数据中，满足 $n, m, k \le 1\,000$。

输出格式

程序应在标准输出上打印 $n$ 行。第 $i$ 行应包含一个整数 $w_i$，表示第 $i$ 个国家的空间站预计在第几次流星雨后收集到至少 $p_i$ 个样本；如果该国家在可预见的未来无法收集到足够的样本，则输出 NIE（波兰语，意为“不”）。

样例

样例输入 1

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

样例输出 1

3
NIE
1