Ban đầu bạn có một mảng \(A\) gồm \(N\) phần tử đều bằng \(0\). Có \(Q\) thao tác cập nhật. Mỗi thao tác cho ba số \(L, R, V\), yêu cầu cộng thêm giá trị \(V\) vào tất cả các phần tử từ chỉ số \(L\) đến \(R\).

Sau khi thực hiện tất cả \(Q\) thao tác, hãy in ra giá trị của mảng \(A\).

Input

• Dòng 1: Hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 2 \cdot 10^5\)).
• \(Q\) dòng tiếp theo: Mỗi dòng chứa 3 số nguyên \(L, R, V\) (\(1 \le L \le R \le N, |V| \le 10^9\)).

Output

• In ra \(N\) số nguyên là giá trị của mảng \(A\) sau khi cập nhật, cách nhau bởi dấu cách.

Example

5 3
1 3 2
2 4 3
4 5 -1

2 5 5 2 -1

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N, Q \le 2000\).
• Subtask \(2\) (\(60\%\) số điểm): \(N, Q \le 2 \cdot 10^5\).