Cho mảng \(A\) có \(n\) phần tử. Có \(Q\) truy vấn, mỗi truy vấn yêu cầu tăng giá trị các phần tử trong đoạn \([L;R]\) lên \(K\).

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_i\).
• \(Q\) dòng tiếp theo, mỗi dòng gồm 3 số nguyên \(L, R, K\).

Output

• In ra trên một dòng \(N\) số nguyên là mảng \(A\) sau khi thực hiện \(Q\) truy vấn.

Constraints

• \(1\le N, Q \le 10^5\).
• \(1\le A_i, K < 10^9\).

Example

Input

4 2
1 0 2 1
1 3 1
1 2 1

Output

3 2 3 1