Sắp xếp đoạn

Bạn được cho một mảng \(w\) gồm \(N\) số nguyên không âm.
Có \(M\) truy vấn, truy vấn thứ \(j\) cho bởi ba số \((l_j, r_j, k_j)\).

Với mỗi truy vấn, hãy kiểm tra xem có thể sắp xếp đoạn

thành dãy không giảm hay không, nếu chỉ được phép hoán đổi hai phần tử kề nhau trong đoạn khi tổng của chúng không vượt quá \(k_j\).

Sau mỗi truy vấn, mảng trở lại trạng thái ban đầu.

\InputFile

• Dòng đầu tiên chứa hai số nguyên \(N, M\) (\(1 \le N, M \le 10^6\)).
• Dòng thứ hai chứa \(N\) số nguyên \(w_i\) (\(0 \le w_i \le 10^9\)).
• Mỗi dòng trong \(M\) dòng tiếp theo chứa ba số \(l_j, r_j, k_j\) (\(1 \le l_j \le r_j \le N\), \(0 \le k_j \le 2\cdot 10^9\)).

\OutputFile
Với mỗi truy vấn, in ra 1 nếu có thể sắp xếp đoạn, và 0 nếu không thể.

\Scoring

• Subtask 1 (8 điểm): \(1 \le N, M \le 500\).
• Subtask 2 (9 điểm): \(1 \le N, M \le 5000\).
• Subtask 3 (13 điểm): \(1 \le N, M \le 10^6\), \(0 \le k_j < w_i\) với mọi \(i\).
• Subtask 4 (23 điểm): \(l_i=1, r_i=n\) với mọi \(i\).
• Subtask 5 (24 điểm): \(1 \le N, M \le 2\cdot 10^5\).
• Subtask 6 (23 điểm): Không có ràng buộc bổ sung.

Example

5 2
3 5 1 8 2
1 3 6
2 5 3

1
0