Cho mảng gồm n số 0. Có q thao tác, mỗi thao tác cho 3 số l,r,x với ý nghĩa là cộng x vào mọi a[i] với l≤i≤r. In ra mảng cuối cùng.

Dữ liệu vào:

• Dòng đầu gồm chứa 2 số nguyên dương n, q;
• q dòng tiếp theo, mỗi dòng gồm 4 số nguyên dương ~l, r, x~.

Kết quả

Ghi ra dãy n số sau khi thực hiện q thao tác.

Ràng buộc:

• ~1\le n, q\le10^5~
• ~|x|\le10^6~

Ví dụ

Input

6 2
1 3 1
3 6 2

Output

1 1 3 2 2 2