쓸어담기

$N$ 개의 아이템 가게가 일렬로 배치되어 있다. 모든 가게에서는 동일한 아이템 한 가지만 사거나 팔 수 있다. 단, 가게마다 아이템의 가격은 다를 수 있다.

럭셔리 마리드는 바쁜 캐릭터라서 쓸어담기라는 방법을 이용해 아이템을 사고 팔며 최대의 이익을 얻으려고 한다. 쓸어담기 방법이란 $i$ 번째부터 $j$ 번째까지의 가게들을 정한 다음, $i$ 번째부터 $j$ 번째 가게에서는 아이템을 하나씩 사고, $j$ 번째 가게에서 모든 아이템을 파는 방식이다.

$Q$ 개의 쿼리가 주어진다. 각 쿼리는 $L$, $R$의 범위와 끝점 $X$로 구성된다. 이는 쓸어담기를 할 때, $i$의 범위가 $L$ 이상 $R$ 이하여아하고, $j$는 $X$와 동일해야 함을 의미한다. 이때, 쿼리마다 최대의 이익을 구하는 프로그램을 작성하시오.

이익을 얻을 수 있는 거래가 없는 경우 아무것도 하지 않을 수 있음에 유의하라.

입력 형식

첫 줄에 가게의 수 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. ($1 \leq N, Q \leq 500\,000$)

그다음 줄에 $N$ 개의 정수 $P_1, \cdots, P_N$가 공백으로 구분되어 주어진다. 이는 $i$ 번째 가게에서 개당 아이템의 가격은 $P_i$임을 의미한다. ($1 \le P_i \le 1\,000\,000$)

이어지는 $Q$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 쿼리에 대한 정보를 나타내는 세 개의 정수 $L$, $R$, $X$가 공백으로 구분되어 주어진다. ($1 \le L \le R \le X \le N$)

출력 형식

$Q$ 개의 줄에 걸쳐 답을 출력한다. $i$ 번째 줄에 $i$ 번째 쿼리에 대한 답을 출력한다.

이익을 얻을 수 없는 경우 거래를 전혀 하지 않을 수도 있고, 이때의 답은 $0$임에 유의하라.

예제

7 5
2 5 6 5 2 1 7
1 4 7
1 3 4
2 3 3
4 6 7
1 4 6

21
2
1
13
0

예제 설명

첫 번째 쿼리의 경우, $1$ 번째 가게부터 $7$ 번째 가게까지 $7$ 개의 가게에서 아이템을 모두 산 후, $7$ 번째 가게에서 아이템을 모두 팔면 $5+2+1+2+5+6+0 = 21$만큼의 이익을 얻을 수 있다. 이보다 더 많은 이익을 낼 수 있는 쓸어담기는 존재하지 않는다.

마지막 쿼리의 경우, 어떠한 쓸어담기 방법으로도 이익을 낼 수 없으므로, 답은 $0$이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설