Làng JOI có \(N\) khu dân cư, đánh số từ \(1\) đến \(N\) và nằm trên một đường thẳng. Hiện tại, mỗi khu đều đang có cháy. Tại thời điểm \(0\), cường độ đám cháy ở khu thứ \(i\) (\(1 \le i \le N\)) là \(S_i\), với \(S_i>0\).

Từ thời điểm \(0\), gió thổi theo hướng từ khu thứ \(1\) đến khu thứ \(N\). Xét mỗi cặp khu kề nhau: nếu tại thời điểm \(t \ge 0\), đám cháy ở khu phía đầu gió mạnh hơn đám cháy ở khu phía cuối gió, thì tại thời điểm \(t+1\), cường độ đám cháy ở khu phía cuối gió sẽ bằng cường độ ở khu phía đầu gió tại thời điểm \(t\). Ngược lại, cường độ ở khu phía cuối gió không thay đổi.

Cụ thể, gọi \(S_i(t)\) là cường độ đám cháy ở khu thứ \(i\) tại thời điểm \(t\). Với mọi \(1 \le i \le N\) và mọi thời điểm nguyên \(t \ge 1\):

Quy ước \(S_0(t)=0\) với mọi \(t \ge 0\), và \(S_i(0)=S_i\) với mọi \(1 \le i \le N\).

Bạn là một lính cứu hỏa và có \(Q\) phương án dập lửa. Bạn dự định chỉ thực hiện một trong số đó. Trong phương án thứ \(j\) (\(1 \le j \le Q\)), tại thời điểm \(T_j\), bạn dùng chất chữa cháy để dập lửa ở tất cả các khu thứ \(k\) thỏa mãn \(L_j \le k \le R_j\). Để dập đám cháy có cường độ \(s\) trong một khu, cần \(s\) lít chất chữa cháy. Vì vậy, lượng chất chữa cháy cần cho phương án thứ \(j\), tính bằng lít, là:

Để lựa chọn phương án thực hiện, bạn muốn biết lượng chất chữa cháy cần thiết cho từng phương án. Các phương án được xét độc lập, không thực hiện liên tiếp.

Cho cường độ các đám cháy tại thời điểm \(0\) và thông tin các phương án, hãy tính lượng chất chữa cháy cần thiết cho mỗi phương án.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả giá trị đều là số nguyên.

N Q
S_1 ... S_N
T_1 L_1 R_1
...
T_Q L_Q R_Q

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa lượng chất chữa cháy, tính bằng lít, cần cho phương án thứ \(j\).

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le Q \le 200\,000\).
• \(1 \le S_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
• \(1 \le T_j \le N\) với \(1 \le j \le Q\).
• \(1 \le L_j \le R_j \le N\) với \(1 \le j \le Q\).

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung. Chỉ nhận được điểm của một nhóm nếu vượt qua tất cả bộ dữ liệu trong nhóm đó.

1. \(1\) điểm: \(N \le 200\) và \(Q \le 200\)
2. \(6\) điểm: \(T_1=T_2=\cdots=T_Q\)
3. \(7\) điểm: \(L_j=R_j\) với mọi \(1 \le j \le Q\)
4. \(6\) điểm: \(S_i \le 2\) với mọi \(1 \le i \le N\)
5. \(80\) điểm: Không có

Ví dụ

5 5
9 3 2 6 5
1 1 3
2 1 5
3 2 5
4 3 3
5 3 5

21
39
33
9
27

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

28
21
34
4
64
43
55
9
27
9

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

9
9
3
4
3
4
5
9
9
9

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

28
27
34
4
64
43
55
9
27
9

20 20
2 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1
1 1 14
2 3 18
4 10 15
8 2 17
9 20 20
4 8 19
7 2 20
11 1 5
13 2 8
20 1 20
2 12 15
7 1 14
12 7 18
14 2 17
9 19 20
12 12 12
6 2 15
11 2 15
19 12 17
4 1 20

25
30
12
32
2
24
38
10
14
40
8
28
24
32
4
2
28
28
12
40

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2019/2020 ngày 9 tháng 2 năm 2020. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.