Mượn Phòng Học

Trường Hogwarts có $N$ ngày trong học kỳ, được đánh số từ $1$ đến $N$. Vào ngày thứ $i$, trường có $r_i$ phòng học trống có thể cho mượn.

Có $M$ giáo sư lần lượt gửi yêu cầu mượn phòng. Giáo sư thứ $j$ cần mượn $d_j$ phòng học cho mỗi ngày từ ngày $s_j$ đến ngày $t_j$ (bao gồm cả hai ngày đầu và cuối). Các yêu cầu được xử lý theo thứ tự từ $1$ đến $M$: mỗi yêu cầu chỉ được chấp nhận nếu trong mọi ngày thuộc khoảng $[s_j,t_j]$, tổng số phòng đã được phân bổ (bao gồm cả yêu cầu hiện tại) không vượt quá số phòng trống.

Hãy tìm yêu cầu đầu tiên không thể được đáp ứng. Nếu tất cả các yêu cầu đều được đáp ứng, in ra $0$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $M$ — số ngày trong học kỳ và số yêu cầu mượn phòng.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa một số nguyên $r_i$ — số phòng trống vào ngày thứ $i$.
• $M$ dòng tiếp theo, dòng thứ $j$ chứa ba số nguyên $d_j$, $s_j$, $t_j$ — số phòng cần mượn, ngày bắt đầu và ngày kết thúc của yêu cầu thứ $j$.

Dữ liệu ra

In ra một số nguyên duy nhất:

• Nếu tất cả các yêu cầu đều được đáp ứng, in $0$.
• Ngược lại, in số thứ tự (đánh số từ $1$) của yêu cầu đầu tiên không thể được đáp ứng.

Ràng buộc

• $1\le N,M\le {10}^6$
• $1\le r_i\le {10}^9$
• $1\le d_j\le {10}^9$
• $1\le s_j\le t_j\le N$

Ví dụ

Ghi chú

Trong ví dụ 1, giáo sư McGonagall mượn 2 phòng cho ngày 1-3, sau đó giáo sư Flitwick muốn mượn 3 phòng cho ngày 2-4. Vào ngày 3, chỉ còn $4-2=2$ phòng trống, không đủ cho 3 phòng mà giáo sư Flitwick yêu cầu. Do đó yêu cầu thứ 2 là yêu cầu đầu tiên bị từ chối.