¡Bajtocja planea atacar Bitocja de nuevo! El desembarco en territorio enemigo es una tarea para verdaderos tipos duros, por lo que participarán los soldados de la mejor unidad especial de Bajtocja: Bajtogrom.

En la sesión informativa del general Bajtczak se reunieron $n$ soldados, quienes gracias a muchos años de entrenamiento de instrucción se formaron instantáneamente en una fila, lo que permite numerarlos de izquierda a derecha con números enteros del 1 al $n$. El general desea elegir un cierto número de escuadrones que enviará al territorio de Bitocja. Como estratega experimentado, sabe que sus subordinados se formaron en ese orden por una razón, debido a las relaciones amistosas entre ellos, por lo que cada escuadrón que elija debe consistir exactamente en $k$ soldados que ocupen un intervalo contiguo de posiciones en la fila. Gracias a esto, puede estar seguro de que los soldados unidos en escuadrones cooperarán bien. Por supuesto, cada soldado puede pertenecer a lo sumo a un escuadrón, pero el general no tiene preferencias sobre el número de escuadrones; en particular, puede no elegir ninguno y renunciar al ataque a Bitocja (al menos por ahora).

El general Bajtczak conoce las habilidades de sus soldados: puede describir a cada uno de ellos con un número entero $a_i$. Cuanto más alto sea, más eficiente es el soldado en combate. Este número también puede ser negativo, lo que significa que el soldado probablemente solo obstaculizará la operación.

El general desea maximizar la suma de los valores $a_i$ de todos los soldados que serán enviados al desembarco. Sin embargo, hay un inconveniente. Puede suceder que tenga que enviar a un cierto número de los primeros soldados de la fila al frente con Intocja, y a un cierto número de los últimos soldados de la fila a misiones de inteligencia en Longlongtocja. En ese caso, tendrá que elegir los escuadrones únicamente entre los soldados cuyos números de posición estén contenidos en el intervalo $[l_i, r_i]$.

Ayuda al general a considerar varios escenarios y, para cada uno de ellos, calcula la suma máxima posible de los valores $a_i$ de los soldados enviados al desembarco.

Entrada

La primera línea de la entrada contiene tres números enteros $n, k$ y $q$ ($1 \le n, q \le 3 \cdot 10^5$; $1 \le k \le n$), que representan, respectivamente, el número de soldados en la fila, el número de soldados en cada escuadrón y el número de escenarios considerados por el general.

La segunda línea contiene $n$ números enteros $a_1, \dots, a_n$ ($-10^9 \le a_i \le 10^9$) descritos en el enunciado del problema.

En las siguientes $q$ líneas hay dos números enteros cada una. La $i$-ésima de estas líneas contiene los números $l_i$ y $r_i$ ($1 \le l_i \le r_i \le n$). Estos significan que en el $i$-ésimo escenario, solo se pueden enviar al desembarco soldados con números de posición que se encuentren en el intervalo $[l_i, r_i]$.

Salida

La salida debe contener $q$ líneas. En la $i$-ésima de ellas debe haber un único número entero que represente la suma máxima de los valores $a_i$ de los soldados enviados a Bitocja en el $i$-ésimo escenario.

Ejemplos

Entrada 1

8 3 7
3 -1 10 0 10 -1 1 -1
1 8
3 5
6 8
1 2
1 7
2 8
1 6

Salida 1

22
20
0
0
22
20
21

Nota

Explicación del ejemplo: En el primer y quinto escenario, el general Bajtczak debería enviar al desembarco dos escuadrones, compuestos por soldados que ocupan las posiciones $[1, 2, 3]$ y $[5, 6, 7]$.

En el segundo y sexto escenario, es óptimo crear solo un escuadrón compuesto por soldados que ocupan las posiciones $[3, 4, 5]$.

En el tercer y cuarto escenario, el general no debería crear ningún escuadrón y pensar con calma en todo el plan de ataque.

En el séptimo escenario, el general debería crear dos escuadrones, compuestos por soldados que ocupan las posiciones $[1, 2, 3]$ y $[4, 5, 6]$.

Subtareas

En algunos grupos de pruebas se cumple que $k \le 30$.