Bajtocja prévoit d'attaquer à nouveau Bitocja ! Le débarquement sur le territoire ennemi est une mission pour de vrais durs à cuire, c'est pourquoi les soldats de la meilleure unité spéciale de Bajtocja, le Bajtogrom, y participeront.

Lors du briefing du général Bajtczak, $n$ soldats se sont rassemblés. Grâce à leurs nombreuses années d'entraînement au pas cadencé, ils se sont instantanément alignés en rang, ce qui permet de les numéroter de gauche à droite par des entiers de $1$ à $n$. Le général souhaite choisir un certain nombre d'escouades qu'il enverra sur le territoire de Bitocja. En tant que stratège expérimenté, il sait que ses subordonnés se sont placés dans cet ordre pour une raison, liée aux relations amicales entre eux. Par conséquent, chaque escouade qu'il choisit doit être composée exactement de $k$ soldats occupant un intervalle contigu de positions dans le rang. Grâce à cela, il peut être sûr que les soldats regroupés en escouades coopéreront bien. Bien entendu, chaque soldat peut appartenir à au plus une escouade, mais le général n'a aucune préférence quant au nombre d'escouades ; en particulier, il peut ne choisir aucune escouade et renoncer à l'attaque sur Bitocja (du moins pour le moment).

Le général Bajtczak connaît les compétences de ses soldats : il peut décrire chacun d'eux par un entier $a_i$. Plus cette valeur est élevée, plus le soldat est efficace au combat. Ce nombre peut également être négatif, ce qui signifie que le soldat ne fera probablement que gêner l'opération.

Le général souhaite maximiser la somme des valeurs $a_i$ de tous les soldats envoyés au débarquement. Il y a cependant un piège. Il peut arriver qu'il doive envoyer un certain nombre des premiers soldats du rang sur le front avec Intocja, et un certain nombre des derniers soldats du rang pour des missions de renseignement à Longlongtocja. Dans ce cas, il devra choisir les escouades uniquement parmi les soldats dont les numéros de position sont compris dans l'intervalle $[l_i, r_i]$.

Aidez le général à examiner différents scénarios et, pour chacun d'eux, calculez la somme maximale possible des valeurs $a_i$ des soldats envoyés au débarquement.

Entrée

La première ligne de l'entrée contient trois entiers $n, k$ et $q$ ($1 \le n, q \le 3 \cdot 10^5$ ; $1 \le k \le n$), représentant respectivement le nombre de soldats dans le rang, le nombre de soldats dans chaque escouade et le nombre de scénarios examinés par le général.

La deuxième ligne contient $n$ entiers $a_1, \dots, a_n$ ($-10^9 \le a_i \le 10^9$) décrits dans l'énoncé.

Les $q$ lignes suivantes contiennent chacune deux entiers. La $i$-ième de ces lignes contient les nombres $l_i$ et $r_i$ ($1 \le l_i \le r_i \le n$). Ils signifient que dans le $i$-ième scénario, seuls les soldats dont les numéros de position se situent dans l'intervalle $[l_i, r_i]$ peuvent être envoyés au débarquement.

Sortie

La sortie doit contenir $q$ lignes. La $i$-ième ligne doit contenir un seul entier, représentant la somme maximale des valeurs $a_i$ des soldats envoyés à Bitocja dans le $i$-ième scénario.

Exemples

Entrée 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

Sortie 1

22
20
0
0
22
20
21

Remarque

Explication de l'exemple : Dans le premier et le cinquième scénario, le général Bajtczak devrait envoyer au débarquement deux escouades, composées des soldats occupant les positions $[1, 2, 3]$ et $[5, 6, 7]$.

Dans le deuxième et le sixième scénario, il est optimal de créer une seule escouade composée des soldats occupant les positions $[3, 4, 5]$.

Dans le troisième et le quatrième scénario, le général ne devrait créer aucune escouade et réfléchir tranquillement à l'ensemble du plan d'attaque.

Dans le septième scénario, le général devrait créer deux escouades, composées des soldats occupant les positions $[1, 2, 3]$ et $[4, 5, 6]$.

Sous-tâches

Dans certains groupes de tests, $k \le 30$.