화재

JOI 마을에는 1번부터 N번까지 N개의 구역이 일렬로 늘어서 있다. 모든 구역에서 화재가 발생한다. 시각 0에 i번 구역의 화재 세기는 S_i이다 (S_i > 0).

시각 0에 바람이 1번 구역에서 N번 구역 쪽으로 분다. 이웃한 구역 쌍마다, 시각 t (t ≥ 0)에 바람 상류 구역의 화재가 하류 구역의 화재보다 강하면 하류 구역의 시각 t+1 화재 세기는 상류 구역의 시각 t 세기가 된다. 그렇지 않으면 하류 구역의 세기는 그대로다. i번 구역의 시각 t 화재 세기를 S_i(t)라 하면 다음이 성립한다.

$S_i(t) = \max\{S_{i-1}(t-1), S_i(t-1)\} \quad (t \geq 1)$

여기서 모든 t ≥ 0에 대해 S_0(t) = 0이고, S_i(0) = S_i이다.

당신은 소방관이며 Q개의 진화 계획이 있고, 그중 정확히 하나만 실행한다. j번째 계획에서는 L_j ≤ k ≤ R_j인 모든 k번 구역에 소화제를 뿌린다. 세기가 s인 화재를 끄려면 소화제 s리터가 필요하다. 따라서 j번째 계획에 필요한 소화제는 S_{L_j}(T_j) + S_{L_j+1}(T_j) + ... + S_{R_j}(T_j) 리터이다. 각 계획에 필요한 소화제의 양을 구하라.

첫 줄에 N과 Q가 주어진다. 둘째 줄에 S_1, S_2, ..., S_N이 주어진다. 이어지는 Q개의 줄에는 각각 T_j, L_j, R_j가 주어진다.

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

Q줄을 출력한다. j번째 줄에는 j번째 계획에 필요한 소화제의 양을 출력한다.

• 1 ≤ N ≤ 200 000
• 1 ≤ Q ≤ 200 000
• 1 ≤ S_i ≤ 1 000 000 000 (1 ≤ i ≤ N)
• 1 ≤ T_j ≤ N (1 ≤ j ≤ Q)
• 1 ≤ L_j ≤ R_j ≤ N (1 ≤ j ≤ Q)