Cho một mảng \(a\) gồm \(n\) số nguyên.

Có \(q\) truy vấn. Mỗi truy vấn gồm ba số nguyên \(l, r, x\). Với mỗi truy vấn, ta thay tất cả phần tử \(a_i\) có giá trị nằm trong đoạn \([l, r]\) thành \(x\).

Đầu tiên, bạn cần in ra tổng của dãy \(a\) ban đầu. Sau mỗi truy vấn, hãy in ra tổng các phần tử trong mảng sau khi thực hiện thay đổi.

Input

• Dòng đầu tiên gồm hai số nguyên \(n, q\).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\).
• \(q\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(l, r, x\).

Output

In ra \(q + 1\) dòng:

• Dòng đầu tiên là tổng ban đầu của mảng.
• Dòng thứ \(i + 1\) là tổng của mảng sau truy vấn thứ \(i\).

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(0 \le q \le 2 \cdot 10^5\)
• \(0 \le a_i \le 10^9\)
• \(0 \le x \le 10^9\)
• \(0 \le l \le r \le 10^9\)

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(q = 0\).
• Subtask \(2\) (\(20\%\) số điểm): \(n, q \le 2000\).
• Subtask \(3\) (\(20\%\) số điểm): \(l = r \le 2 \cdot 10^5\) và \(a_i, x \le 2 \cdot 10^5\).
• Subtask \(4\) (\(10\%\) số điểm): \(l = r\).
• Subtask \(5\) (\(20\%\) số điểm): \(x = 0\).
• Subtask \(6\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

6 4
2 5 5 8 10 1
5 5 3
1 3 7
7 10 0
4 6 2

31
27
46
0
0

5 3
100 200 300 400 500
150 350 50
50 100 10
10 500 1

1500
1100
930
5