Cho mảng ~a~ gồm ~n~ phần tử. Có ~q~ truy vấn, mỗi truy vấn gồm ba tham số ~l~, ~r~ và ~x~ với ý nghĩa: tăng đoạn con liên tiếp từ ~l~ tới ~r~ trong mảng lên ~x~ đơn vị.

Yêu cầu: In ra mảng sau ~q~ truy vấn.

Input

Dòng đầu tiên ghi hai số nguyên dương ~n~ và ~q~ (~1 \le n, q \le 2 \times 10^5~), là số phần tử của mảng ~a~ và số truy vấn.

Dòng thứ hai ghi ~n~ số nguyên dương ~a_i~ (~1 \le a_i \le 10^9~), là giá trị ban đầu của mảng.

~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~l~, ~r~, ~x~ (~1 \le l \le r \le n~, ~1 \le x \le 10^9~) mô tả từng truy vấn.

Output

Mảng sau ~q~ truy vấn.

Sample Input 1

5 3
1 3 8 2 1
1 3 2
1 4 2
5 5 1

Sample Output 1

5 7 12 4 2

Notes

Sau truy vấn 1, mảng là ~[3, 5, 10, 2, 1]~.

Sau truy vấn 2, mảng là ~[5, 7, 12, 4, 1]~.

Sau truy vấn 3, mảng là ~[5, 7, 12, 4, 2]~.