Mô tả và yêu cầu

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.

Dữ liệu vào

- 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                      Output
                         8 7                        -1 6 5 6 7 2 1 6
                         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
      Giới Hạn:
          N, Q ≤ 1e6
          1 ≤ A[i] ≤ 1e9
          L ≤ R ≤ N, S ≤ 1e9.