유성

성간 연합(Byteotian Interstellar Union, BIU)이 어느 은하계 근처에서 새로운 행성을 발견했다. 이 행성에는 유성우가 자주 내려 사람이 살기에는 적합하지 않지만, 유성우를 연구하기에는 더없이 좋은 장소로 밝혀졌다.

BIU 회원국들은 이미 이 행성 가까이에 우주 정거장을 세웠다. 정거장의 목적은 유성우가 남긴 운석 샘플을 채취하는 것이다. 행성의 궤도는 원형이며 1번부터 M번까지 번호가 붙은 M개의 구역으로 나뉜다. 궤도가 원형이므로 1번 구역과 M번 구역은 서로 인접해 있다. 각 구역은 N개의 회원국이 나누어 소유한다.

각 회원국은 모으려는 운석 샘플의 목표치를 정해 두었다. 유성우 예보가 주어졌을 때, 각 회원국이 목표치를 언제 달성할 수 있는지 구하여라.

첫째 줄에 두 정수 N, M ($1 \le N, M \le 300{,}000$)이 주어진다. N은 회원국의 수, M은 궤도 구역의 수이다.

둘째 줄에는 M개의 정수 $o_1, o_2, \dots, o_M$ ($1 \le o_i \le N$)이 주어진다. $o_i$는 i번째 구역을 소유한 회원국의 번호이다.

셋째 줄에는 N개의 정수 $p_1, p_2, \dots, p_N$ ($1 \le p_j \le 10^9$)이 주어진다. $p_j$는 j번째 회원국이 목표로 하는 운석 샘플의 수량이다.

넷째 줄에는 정수 Q ($1 \le Q \le 300{,}000$)가 주어진다. Q는 유성우 예보의 수이다.

이어지는 Q개의 줄에는 날짜 순서대로 유성우 예보가 주어진다. u번째 줄은 세 정수 $l_u$, $r_u$, $a_u$ ($1 \le l_u, r_u \le M$, $1 \le a_u \le 10^9$)로 이루어진다. $l_u \le r_u$이면 구역 $l_u, l_u+1, \dots, r_u$에, $l_u > r_u$이면 구역 $l_u, l_u+1, \dots, M, 1, \dots, r_u$에 각각 $a_u$개의 운석이 내린다. 이 예보는 예보 시작 후 u번째 날에 일어난다.

각 회원국이 목표치를 달성하는 데 필요한 최소 일수 $w_j$를 회원국 번호 순서대로 한 줄에 하나씩 출력한다. $w_j$번째 날이 끝났을 때, j번째 회원국이 소유한 구역들에 내린 운석 샘플의 총합이 $p_j$개 이상이어야 한다. Q일의 예보 기간 안에 목표치를 채우지 못하는 회원국은 그 줄에 NIE(폴란드어로 '아니요'를 뜻한다)를 출력한다.