Cho một mảng A gồm N số nguyên dương. Ta thực hiện M thao tác, mỗi thao tác có dạng như sau: Chọn ra một đoạn [L, R] rồi trừ đi tất cả các phần tử trong đoạn [L, R] cho s. Với mỗi vị trí i ta cần xác định thời điểm thao tác đầu tiên mà ~A[i] ≤ 0~.

Input:

• Dòng đầu tiên gồm ~N~ và ~M~.
• Dòng tiếp theo gồm ~N~ số nguyên.
• ~M~ dòng tiếp theo, mỗi dòng gồm 3 số nguyên ~L, R, S~.

Output: Gồm ~N~ số nguyên, mỗi số nguyên ghi nhận thời điểm đầu tiên mà giá trị ~A[i] ≤ 0~. Nếu không tồn tại thời điểm ~A[i] ≤ 0~ sau ~M~ thao tác ta sẽ in ra -1.

Ví dụ:

Input

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

Output

-1 6 5 6 7 2 1 6

Giới Hạn:

• ~N, Q ≤ 1e6~
• ~1 ≤ A[i] ≤ 1e9~
• ~L ≤ R ≤ N, S ≤ 1e9~.