Shine đang ôn luyện để chuẩn bị cho kì thi ICPC sắp tới, chủ đề ôn luyện hôm nay của Shine là các bài liên quan tới mảng và các truy vấn. Thấy bạn mình đang học như vậy, QioCas liền đánh đố một bài toán cho bạn mình giải quyết, bài toán được phát biểu như sau:

• Cho một mảng gồm ~N~ phần tử ~a_1, a_2, \dots, a_N~. Ta có ~Q~ truy vấn có dạng l r x với ý nghĩa ~a_i = max(a_i, x)~ với mọi ~l \le i \le r~.

Nếu bài toán chỉ dừng lại ở việc sau mỗi truy vấn ta cần in ra tổng của các phần tử trong mảng (hay ~\sum_{i = 1}^N a_i~) thì bài toán lại quá dễ để giải quyết. Do đó ở bài toán này, với truy vấn thứ ~i~, QioCas muốn biết tổng của các phần tử trong mảng khi thực hiện mỗi truy vấn thứ ~i~ và tổng của các phần tử trong mảng khi thực hiện tất cả truy vấn ngoại trừ truy vấn thứ ~i~.

Shine rất giỏi nên nhìn phát ra đã luôn cách làm tuy nhiên do rất lười phải cài một bài toán dễ như vậy nên Shine muốn nhờ các bạn giúp đỡ Shine. Các bạn hãy giúp Shine giải quyết bài toán nhé.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~N, Q\ (1 \le N, Q \le 2 \cdot 10^5)~.

• Dòng thứ ~2~ gồm ~N~ số nguyên ~a_1, a_2, \dots, a_N\ (1 \le a_i \le 2 \cdot 10^9)~

• ~Q~ dòng tiếp theo có dạng l r x ~(1 \le l \le r \le N, 1 \le x \le 2 \cdot 10^9)~

Output

• Gồm ~Q~ dòng, mỗi dòng gồm ~2~ số nguyên là kết quả bài toán.

Scoring

Sample Input 1

5 4
1 2 3 4 5
1 3 3
4 4 4
2 3 4
5 5 10

Sample Output 1

18 23
15 25
18 23
20 20

Notes

Mảng khi thực hiện mỗi truy vấn ~1~, ~a = [3, 3, 3, 4, 5]~.

Mảng khi thực hiện tất cả truy vấn trừ truy vấn ~1~, ~a = [1, 4, 4, 4, 10]~.

Mảng khi thực hiện mỗi truy vấn ~2~, ~a = [1, 2, 3, 4, 5]~.

Mảng khi thực hiện tất cả truy vấn trừ truy vấn ~2~, ~a = [3, 4, 4, 4, 10]~.

Mảng khi thực hiện mỗi truy vấn ~3~, ~a = [1, 4, 4, 4, 5]~.

Mảng khi thực hiện tất cả truy vấn trừ truy vấn ~3~, ~a = [3, 3, 3, 4, 10]~.

~\cdots~