题目描述

Byteotian Interstellar Union 有 $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$ ，表示第 $k$ 场陨石雨的发生地点在从 $l_i$ 顺时针到 $r_i$ 的区间中（如果 $l_i\le r_i$ ，就是 $l_i,l_i+1,\cdots,r_i$，否则就是 $l_i,l_i+1,\cdots,m-1,m,1, 2, ..., r_i$ ），向区间中的每个太空站提供 $a_i$ 单位的陨石样本。

输出格式

输出 $n$ 行。第 $i$ 行的数 $w_i$ 表示第 $i$个国家在第 $w_i$ 波陨石雨之后能够收集到足够的陨石样本。如果到第 $k$ 波结束后仍然收集不到，输出NIE。

输入输出样例 #1

输入 #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

说明/提示

$1\le n,m,k\le 3\cdot10^5$

$1\le p_i,a_i\le 10^9$