Eres un operador bursátil de una empresa de inversión. 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 intervalo $i$ siempre es $a_i$. En cuanto termina el intervalo $n$ de un día, comienza inmediatamente el primer intervalo del día siguiente, y el precio cambia de $a_n$ a $a_1$. Es una oportunidad única en la vida: si simplemente compras y vendes según este patrón que ya has descubierto, ¡hay una forma garantizada de obtener beneficios durante tus horas de trabajo!
Tus horarios de trabajo varían, y un período de trabajo puede prolongarse más allá de la medianoche. Se te dan $q$ períodos de trabajo. El período $i$ comienza en el intervalo $l_i$ y termina en el intervalo $r_i$, incluidos ambos extremos. Los intervalos en orden cronológico son:
- $l_i, l_i + 1, \ldots, r_i$ si $l_i \le r_i$;
- $l_i, l_i + 1, \ldots, n, 1, 2, \ldots, r_i$ si $l_i > r_i$.
En cada período de trabajo puedes completar como máximo $k$ 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. Solo 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 indicado arriba. También puedes no realizar ninguna transacción, obteniendo un beneficio de $0$.
Para cada período de trabajo, halla de forma independiente el beneficio total máximo que puedes obtener.
Entrada
La primera línea contiene tres enteros $n, k, q$ ($1 \le n \le 10^5$, $1 \le k \le 800$, $1 \le q \le 3 \times 10^5$): el número de intervalos de tiempo de un día, el número máximo de transacciones por período de trabajo 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 intervalo de tiempo $i$ de cada día.
Cada una de las siguientes $q$ líneas contiene dos enteros $l_i, r_i$ ($1 \le l_i, r_i \le n$), que describen el período de trabajo $i$.
Sea $\mathrm{len}_i$ el número de intervalos de tiempo de este período. Si $l_i \le r_i$, entonces $\mathrm{len}_i = r_i - l_i + 1$; en caso contrario, $\mathrm{len}_i = n - l_i + 1 + r_i$.
Para cada período de trabajo, $l_i$ y $\mathrm{len}_i$ se generan de forma independiente y uniforme al azar en $[1,n]$ y $[\max(1,\lfloor 0.15n\rfloor),\max(1,\lfloor 0.85n\rfloor)]$, respectivamente. El valor de $r_i$ queda determinado de manera única por $l_i$ y $\mathrm{len}_i$. En particular, cuando el intervalo es $[1,1]$, el resultado aleatorio siempre será $1$.
Hay exactamente 50 casos de prueba, sin contar el ejemplo.
Salida
Imprime $q$ líneas. La línea $i$ debe contener un entero: el beneficio máximo que puedes obtener durante el período de trabajo $i$ con como máximo $k$ transacciones.
Ejemplos
Entrada 1
6 2 3 3 1 4 1 5 9 2 5 5 2 4 4
Salida 1
7 4 0