시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 50 11 6 14.634%

문제

최근 '백준 우주 연합(BIU)'은 어떤 은하계 근처에서 새로운 행성 하나를 발견했다. 그 행성은 유성우가 많이 내려 사람이 살기엔 적절치 못한 곳이었으나, 유성우에 관한 연구 대상으로는 아주 좋은 곳으로 밝혀졌다.

BIU 회원국은 이미 그 행성 가까이에 우주정거장을 세웠다. 이 우주 정거장의 목적은 유성우의 운석 샘플을 채취하는 것이다. BIU연합 최고 지도 사령관인 백준은 행성 궤도를 m개의 구역으로 나누고 1부터 m까지 순서대로 번호를 부여했다. (행성 궤도는 원 궤도이므로 1번 구역과 m번 구역은 서로 인접해 있다.) 각 구역은 N개의 BIU회원국들이 서로 적당히 나눠 가졌다.

각 BIU 회원국들은 모으고자 하는 운석 샘플의 목표치를 정했다. 당신의 임무는 유성우 예보를 바탕으로 각 나라들이 언제 샘플 채취를 완료할 수 있는지 말해주는 것이다.

입력

첫째 줄에 두 정수 N, M(1 ≤ N,M ≤ 300,000)이 주어진다. N은 BIU연합의 회원국 개수고, M은 행성 궤도의 구역 개수이다.

둘째 줄에는 M개의 정수 oi (1 ≤ oi ≤ N)가 주어진다. oi는 i번째 구역을 소유하고 있는 BIU연합의 회원국 번호를 나타낸다.

세 번째 줄에는 N개의 정수 pj (1 ≤ pj ≤ 109)가 주어진다. pj는 j번째 BIU회원국이 목표치로 정한 운석 샘플 수량을 나타낸다.

네 번째 줄에는 정수 k(1 ≤ k ≤ 300,000)가 주어진다. k는 유성우 예보의 수를 나타낸다.

그다음 k개의 줄에는 예측된 유성우의 개수가 날짜 순서로 표시된다. 각 u번째 줄은 세 가지 정수 lu, ru, au로 구성되는데, l≤ ru인 경우 구역 lu,lu+1,…,ru에 au개의 운석이 내리고, lu>ru인 경우 구역 lu,lu+1,…,m,1,…,ru에 au개의 운석이 내린다는 뜻이다. (정수 au의 범위는 1 ≤ au ≤ 10이고, 여기서 u는 유성우 예보 시작 후 u번째 날을 의미한다.)

출력

회원국별로 샘플조사를 끝마칠 수 있는 최소 일 수 wj를 회원국 번호 순서대로 한 줄에 하나씩 출력한다. 끝마치는 날에는 최소한 pj개의 운석 샘플을 가지고 있어야 하며, 유성우 예보 기간 안에 운석 샘플을 다 채우지 못 할 경우 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

힌트