Vous avez la capacité de créer des robots dont la hauteur appartient à $[0, d]$. Pour les tester, vous avez construit une ligne de longueur $n$ contenant des obstacles. La description des obstacles vous est donnée sous la forme d'un tableau $a$. Si $a_i = 0$, alors il n'y a pas d'obstacle à la $i$-ème position ; sinon, il y a un obstacle de hauteur $a_i > 0$.

Pour tester votre robot, vous sélectionnez un segment $[l, r]$ et lui faites traverser tous les obstacles contenus dans ce segment. Lorsque le robot rencontre un obstacle de valeur $a_i > 0$, l'une des deux possibilités suivantes se produit :

• Si la hauteur actuelle du robot $h$ est strictement inférieure à $a_i$, rien ne se passe car le robot est trop petit pour atteindre l'obstacle.
• Si la hauteur actuelle du robot $h$ est au moins égale à $a_i$, sa nouvelle hauteur devient $h' = h - a_i$.

Vous devez maintenant répondre à $q$ requêtes. Pour chacun des $q$ segments $[l_i, r_i]$, vous devez indiquer la hauteur maximale possible avec laquelle le robot peut terminer après avoir traversé les obstacles du segment si sa hauteur initiale a été choisie dans l'intervalle $[0, d]$.

Entrée

La première ligne contient les entiers $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — la longueur du tableau et le nombre de requêtes.

La deuxième ligne contient $n$ entiers $a_i$ ($0 \le a_i \le 10^9$) — la description du tableau.

Les $q$ lignes suivantes contiennent chacune une paire d'entiers $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — la description des requêtes.

Sortie

Affichez $q$ entiers — les réponses aux requêtes.

Exemples

Entrée 1

5 3 5
0 2 6 1 3
5 5
1 5
1 3

Sortie 1

2
2
3

Entrée 2

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

Sortie 2

3
2
3
3
4