이 문제는 A번 문제 「All the Trades Are the Best」의 다른 버전이다. 이 버전에서는 각 근무 기간마다 자체 거래 횟수 제한이 있으며, 각 근무 기간은 하루 안에 완전히 포함된다. 근무 기간이 무작위로 생성될 필요는 없다.

당신은 투자 회사의 트레이더이다. 어느 날, 거래를 담당하는 주식의 가격이 매일 정확히 같은 패턴을 반복한다는 사실을 발견했다. 하루는 길이가 같은 $n$개의 시간 구간으로 나뉘며, $i$번째 구간의 주가는 항상 $a_i$이다. 하루의 $n$번째 구간이 끝나면 다음 날의 첫 번째 구간이 바로 이어지고, 주가는 $a_n$에서 $a_1$로 바뀐다. 이것은 일생에 한 번 올 기회이다. 이미 알아낸 이 패턴에 맞춰 근무 시간에 주식을 사고팔기만 한다면, 확실하게 이익을 얻을 수 있다!

서로 독립적인 $q$개의 근무 기간이 주어진다. $i$번째 기간은 시간 구간 $l_i$에서 시작하여 시간 구간 $r_i$에서 끝나며, 양 끝 구간을 모두 포함한다. 여기서 $l_i \le r_i$이다. 시간순으로 나열한 구간은 $l_i, l_i + 1, \ldots, r_i$이다.

$i$번째 근무 기간에는 최대 $k_i$번의 거래를 완료할 수 있다. 각 거래는 주식 한 주를 매수하고 이후의 시간 구간에 매도하는 것으로 이루어지며, 이익은 매도 가격에서 매수 가격을 뺀 값이다. 한 번에 최대 한 주만 보유할 수 있으므로, 다른 주식을 매수하기 전에 현재 보유한 주식을 매도해야 한다. 모든 매수와 매도는 해당 근무 기간 안에서 이루어져야 하며, 위에 나열한 시간순서를 따라야 한다. 거래를 전혀 하지 않아 $0$의 이익을 얻을 수도 있다.

각 근무 기간에 대해, 얻을 수 있는 최대 총이익을 독립적으로 구하여라.

입력

첫 번째 줄에는 두 정수 $n, q$ ($1 \le n \le 10^5$, $1 \le q \le 10^5$)가 주어진다. 이들은 각각 하루의 시간 구간 수와 근무 기간 수이다.

두 번째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$)이 주어진다. $a_i$는 매일 $i$번째 시간 구간의 주가이다.

다음 $q$개의 줄에는 각각 세 정수 $l_i, r_i, k_i$ ($1 \le l_i \le r_i \le n$, $0 \le k_i \le \lfloor (r_i - l_i + 1)/2 \rfloor$)가 주어지며, $i$번째 근무 기간과 그 거래 횟수 제한을 나타낸다.

근무 기간이나 거래 횟수 제한의 무작위성은 보장되지 않는다.

출력

$q$개의 줄을 출력하여라. $i$번째 줄에는 $i$번째 근무 기간 동안 최대 $k_i$번의 거래로 얻을 수 있는 최대 이익을 나타내는 정수 하나를 출력하여라.

예제

입력 1

6 7
3 1 4 1 5 9
1 6 1
1 6 2
1 6 3
2 5 1
2 5 2
4 4 0
1 6 0

출력 1

8
11
11
4
7
0
0

참고

첫 번째 질의에서는 시간 구간 $2$에 매수하고 시간 구간 $6$에 매도하여 $9 - 1 = 8$의 이익을 얻는다.

두 번째 질의에서는 시간 구간 $2$에 매수하고 시간 구간 $3$에 매도한 뒤, 시간 구간 $4$에 다시 매수하고 시간 구간 $6$에 매도한다. 총이익은 $(4 - 1) + (9 - 1) = 11$이다. 세 번째 질의에서 세 번째 거래를 허용해도 최대 이익은 증가하지 않는다.

여섯 번째와 일곱 번째 질의에서는 $k_i = 0$이므로 거래가 허용되지 않으며 답은 $0$이다.