Esta es otra versión del problema A, All the Trades Are the Best. En esta versión, cada período de trabajo tiene su propio límite de transacciones y está contenido por completo en un solo día. No se exige que los períodos de trabajo se generen aleatoriamente.

Eres un operador de una empresa de inversiones. Un día descubres que la acción de cuya negociación eres responsable sigue un patrón diario que se repite exactamente: el día se divide en $n$ intervalos de tiempo iguales, y el precio de la acción durante el $i$-ésimo intervalo siempre es $a_i$. Al terminar el $n$-ésimo intervalo de un día, comienza inmediatamente el primer intervalo del día siguiente, y el precio pasa de $a_n$ a $a_1$. ¡Esta es una oportunidad única en la vida: si compras y vendes durante tu horario de trabajo siguiendo este patrón que ya has descubierto, tienes una forma garantizada de obtener beneficios!

Se te dan $q$ períodos de trabajo independientes. El $i$-ésimo período comienza en el intervalo $l_i$ y termina en el intervalo $r_i$, incluidos ambos extremos, donde $l_i\le r_i$. Los intervalos en orden cronológico son $l_i,l_i+1,\ldots,r_i$.

En el $i$-ésimo período de trabajo puedes realizar como máximo $k_i$ transacciones. Cada transacción consiste en comprar una acción y venderla en un intervalo de tiempo posterior, con un beneficio igual al precio de venta menos el precio de compra. Puedes tener como máximo una acción a la vez, por lo que debes vender tu acción actual antes de comprar otra. Todas las compras y ventas deben realizarse dentro de ese período de trabajo y seguir el orden cronológico anterior. También puedes no realizar ninguna transacción y obtener un beneficio de $0$.

Para cada período de trabajo, encuentra de forma independiente el máximo beneficio total que puedes obtener.

Entrada

La primera línea contiene dos enteros $n,q$ ($1\le n\le 10^5$, $1\le q\le 10^5$): el número de intervalos de tiempo de un día y el número de períodos de trabajo, respectivamente.

La segunda línea contiene $n$ enteros $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^6$), donde $a_i$ es el precio de la acción en el $i$-ésimo intervalo de tiempo de cada día.

Cada una de las siguientes $q$ líneas contiene tres enteros $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$), que describen el $i$-ésimo período de trabajo y su límite de transacciones.

No hay ninguna garantía de aleatoriedad para los períodos de trabajo ni para sus límites de transacciones.

Salida

Imprime $q$ líneas. La $i$-ésima línea debe contener un entero: el máximo beneficio que puedes obtener durante el $i$-ésimo período de trabajo realizando como máximo $k_i$ transacciones.

Ejemplos

Entrada 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

Salida 1

8
11
11
4
7
0
0

Nota

En la primera consulta, compra en el intervalo $2$ y vende en el intervalo $6$, obteniendo $9-1=8$.

En la segunda consulta, compra en el intervalo $2$, vende en el intervalo $3$, vuelve a comprar en el intervalo $4$ y vende en el intervalo $6$. El beneficio total es $(4-1)+(9-1)=11$. Permitir una tercera transacción en la tercera consulta no aumenta el beneficio máximo.

En la sexta y la séptima consultas, $k_i=0$, por lo que no se permite ninguna transacción y la respuesta es $0$.