Necrophos là một cậu bé thích suy nghĩ lung tung. Trong lúc các bạn đang cố gắng học tập các kiến thức khó thì cậu lại muốn đào sâu ý nghĩa của những thứ đơn giản.

Hôm nay cậu để ý đến dãy số ~2, 6, 12, 20, 30, 42, ...~ mà phần tử thứ ~i~ có giá trị bằng ~i*(i+1)~.

Necrophos có tìm ra điều gì không thì không rõ, chỉ biết rằng sau đó cậu đã đi đố các bạn cùng lớp một bài toán như sau: Cho một dãy ~n~ số nguyên ~a_i~, ban đầu tất cả các phần tử có giá trị bằng ~0~. Cho ~q~ truy vấn có dạng:

• ~l~ ~r~ ~k~: Tăng ~a_l~ lên ~(1*2)*k~, tăng ~a_{l+1}~ lên ~(2*3)*k~, tăng ~a_{l+2}~ lên ~(3*4)*k~, ..., tăng ~a_r~ lên ~((r-l+1)*(r-l+2))*k~.

Yêu cầu

Cho ~n~ và ~q~ truy vấn. Sau khi thực hiện ~q~ truy vấn, đưa ra giá trị sau cùng của toàn bộ dãy.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n~, ~q~ ~(1≤n≤10^6, 1≤q≤10^6)~ cách nhau một dấu cách.
• ~q~ dòng sau, mỗi dòng là một truy vấn có dạng ~l~ ~r~ ~k~ ~(1≤l≤r≤n, 1≤k≤10^9)~.

Output

Một dòng duy nhất chứa ~n~ số nguyên ~a_i~ sau khi thực hiện ~q~ truy vấn, mỗi phần tử cách nhau một dấu cách.

Lưu ý: dữ liệu đảm bảo giá trị sau cùng của mỗi phần tử không vượt quá ~10^{18}~.

Sample Input

5 3
1 3 1
2 5 3
2 3 2

Sample Output

2 16 42 36 60

Giải thích

Ban đầu dãy có 5 phần tử là ~[0, 0, 0, 0, 0]~.

Sau truy vấn đầu tiên, dãy trở thành ~[2, 6, 12, 0, 0]~.

Sau truy vấn thứ hai, dãy trở thành ~[2, 12, 30, 36, 60]~.

Sau truy vấn cuối cùng, dãy trở thành ~[2, 16, 42, 36, 60]~.

Subtask

• Có 30% số test ứng với 30% số điểm có ~1≤n,q≤10^3~;
• Có 30% số test ứng với 30% số điểm có ~1≤n,q≤10^5~, mọi truy vấn có ~k=1~;
• Có 20% số test ứng với 20% số điểm có ~1≤n,q≤10^5~;
• 20% số test còn lại tương ứng với 20% số điểm không có giới hạn gì thêm.