Trong thiết kế một trò chơi điện tử mới ra mắt, Breinu là một vương quốc có \(n\) khu vườn hoa hồng tuyệt đẹp được bảo vệ bởi \(n\) toà tháp canh. Các khu vườn và các toà tháp canh được đánh số từ \(1\) đến \(n\). Khu vườn thứ \(i\) được bảo vệ bởi các tháp canh có chỉ số \(i, 2 \times i, 3 \times i, ...\) . Tháp canh thứ \(i\) có chỉ số sức mạnh là \(a_i\). Một tháp canh sẽ bị phá huỷ nếu chỉ số sức mạnh của nó bị giảm xuống nhỏ hơn hoặc bằng \(0\).

Người chơi X đang có kế hoạch chiếm lấy \(n\) khu vườn hoa. Để có thể bắt đầu đánh chiếm một vườn hoa, X cần phá huỷ toàn bộ các tháp canh bảo vệ vườn hoa đó. X sẽ tiến đánh \(q\) lần vào dàn tháp canh, lần tiến đánh thứ \(i\) ảnh hưởng đến các tháp canh có chỉ số từ \(l_{i}\) đến \(r_{i}\) , mỗi tháp canh bị ảnh hưởng sẽ bị trừ đi \(s_{i}\) điểm sức mạnh.

Máy sẽ có nhiệm vụ bảo vệ \(n\) khu vườn này. Do đó cần biết, với mỗi khu vườn, kể từ sau lần bị tấn công nào thì tất cả các tháp canh bảo vệ khu vườn đó bị phá huỷ để có thể điều động quân lính đến bảo vệ.

Yêu cầu: Với mỗi khu vườn, hãy lập trình cho máy tính tính toán lần tấn công đầu tiên mà tất cả các tháp canh bảo vệ khu vườn đó bị phá huỷ.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, q\) \((1 \leq n , q \leq 5 \times 10^5)\) - số khu vườn và số đợt tấn công của X.
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, ..., a_{n}\) \((1 \leq a_{i} \leq 10^{9})\) - chỉ số sức mạnh của các tháp canh.
• \(q\) dòng tiếp theo, dòng thứ \(i\) chứa \(3\) số nguyên \(l_{i}, r_{i}, s_{i}\) \((1 \leq l_{i} \leq r_{i} \leq n, 1 \leq s_{i} \leq 10^{9})\) mô tả một lần tấn công của X.

Output

• In ra \(n\) số nguyên, số nguyên thứ \(i\) là lần tấn công đầu tiên mà kể từ sau đó toàn bộ tháp canh bảo vệ vườn hoa thứ \(i\) bị phá huỷ. Nếu sau toàn bộ \(q\) lần tấn công của X mà vẫn còn lại ít nhất một tháp canh bảo vệ khu vườn này, in ra \(-1\).

Scoring

• Subtask \(1\) (\(19\) điểm): \(n, q \leq 5 \times 10^{2}\)
• Subtask \(2\) (\(29\) điểm): \(n, q \leq 5 \times 10^{3}\)
• Subtask \(3\) (\(23\) điểm): \(n, q \leq 10^{5}\)
• Subtask \(4\) (\(29\) điểm): Không có rằng buộc gì thêm

Example

8 7
4 5 2 2 9 6 2 8
5 8 3
5 7 4
3 4 1
2 2 4
2 4 2
8 8 9
2 7 5

-1 6 5 6 7 2 1 6