Mưa Thiên Thạch

Một quỹ đạo tròn được chia thành $m$ khu vực đánh số $1,\dots ,m$; khu vực $m$ kề khu vực $1$. Mỗi khu vực có đúng một trạm, thuộc một trong $n$ quốc gia. Quốc gia $i$ muốn thu ít nhất $p_i$ mẫu.

Có $k$ sự kiện theo thứ tự thời gian. Sự kiện $(l,r,a)$ cộng $a$ mẫu cho mỗi trạm trên cung từ $l$ đến $r$:

• nếu $l\le r$, cung gồm các khu vực $l,l+1,\dots ,r$;
• nếu $l>r$, cung đi qua điểm vòng và gồm $l,l+1,\dots ,m,1,2,\dots ,r$.

Với mỗi quốc gia, hãy tìm sự kiện sớm nhất mà tổng mẫu tại tất cả trạm của quốc gia đạt ít nhất mục tiêu. Một quốc gia có thể không sở hữu trạm nào.

Input

• Dòng đầu chứa $n$ và $m$: số quốc gia và số khu vực.
• Dòng thứ hai chứa $m$ số oi, trong đó oi là quốc gia sở hữu trạm ở khu vực $i$.
• Dòng thứ ba chứa $n$ mục tiêu $p_1,p_2,\dots ,p_n$.
• Dòng thứ tư chứa số sự kiện $k$.
• $k$ dòng tiếp theo, mỗi dòng chứa $l,r,a$ theo thứ tự thời gian.

Output

• Với mỗi quốc gia từ $1$ đến $n$, in chỉ số sự kiện sớm nhất làm tổng mẫu đạt mục tiêu; in NIE nếu sau toàn bộ sự kiện vẫn chưa đạt.

Constraints

• $1\le n,m,k\le 3\cdot 10^5$.
• $1\le oi\le n$.
• $1\le pi\le 10^9$.
• $1\le l,r\le m$ và $1\le a\le 10^9$.
• Nếu $l\le r$, sự kiện tác động các khu vực $l,\dots ,r$; nếu $l>r$, sự kiện tác động $l,\dots ,m$ và $1,\dots ,r$.
• Một quốc gia có thể không sở hữu trạm nào.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m,k\le 1000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

2
3
4
3
NIE