Một cơn mưa lớn trút xuống \(n\) thùng xô xếp thành hàng. Trong \(q\) đợt mưa, đợt thứ \(i\) làm tăng lượng nước trong các thùng từ \(l_i\) đến \(r_i\) thêm \(k_i\) lít.

Hãy tính lượng nước trong mỗi thùng sau \(q\) đợt mưa.

Gợi ý: Dùng difference array: \(diff[l] += k\), \(diff[r+1] -= k\). Sau đó tính prefix sum trên \(diff\) để khôi phục mảng.

Input

Dòng đầu chứa \(n\) và \(q\) (\(1 \le n, q \le 10^5\)). \(q\) dòng tiếp theo, mỗi dòng chứa \(l, r, k\) (\(1 \le l \le r \le n\), \(1 \le k \le 10^9\)).

Output

In ra \(n\) số — lượng nước trong mỗi thùng, cách nhau bởi khoảng trắng.

Example

5 3
1 3 5
2 4 3
3 5 2

Output:

5 8 10 5 2