expozitie

O expoziţie de pictură este organizată într-o clădire circulară formată din $N + 1$ săli numerotate de la $0$ la $N$ în sens trigonometric. Iniţial, toate sălile sunt goale. Prima sală este numerotată cu $0$ şi în ea intră câte $Y$ oameni în fiecare minut. Următoarele $N$ săli au uşi de ieşire. Din sala $i$, $1 \leq i \leq N$ vor ieşi în fiecare minut $x_i$ oameni, dar numai dacă există cel puţin $x_i$ oameni în sala respectivă. După ce intră oameni în sala $0$ şi pleacă eventual oameni din celelalte săli, în acelaşi minut, toţi cei rămaşi în expoziţie trec în sala următoare. Mai precis, dacă un om se află în sala $i \leq N - 1$ atunci el trece în sala $i + 1$, iar dacă este în sala $N$ atunci trece în sala $0$.

Cerinţă

Să se scrie un program care pentru numere $N$, $Q$, $y$ cunoscute şi sirul $x_i$, $1 \leq i \leq N$ cunoscut, răspunde la întrebări de forma: „Câţi oameni sunt după $t$ minute în sala $s$?”.

Date de intrare

Fişierul de intrare expozitie.in conţine pe prima linie numerele $N$, $Q$ şi $y$. Pe a doua linie vor exista $N$ numere separate prin câte un spaţiu reprezentând elementele vectorului $x$. Pe următoarele $Q$ linii vor fi descrise cele $Q$ întrebări şi vor conţine câte două numere $t$ şi $s$ separate prin spaţiu reprezentând un număr de minute şi un număr de sală corespunzător unei întrebări.

Date de ieșire

Fişierul de ieşire expozitie.out va conţine $Q$ linii. Pe aceste linii se vor găsi răspunsurile la cele $Q$ întrebări în ordinea în care acestea apar în fişierul de intrare.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$;
• $1 \leq Q \leq 1 \ 000 \ 000$;
• $1 \leq y \leq 1 \ 000$;
• $1 \leq x_i \leq 100$;
• $0 \leq s \leq N$ pentru fiecare întrebare;
• $1 \leq t \leq 1 \ 000 \ 000 \ 000$ pentru fiecare întrebare;

Exemplu

expozitie.in

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

expozitie.out

0
4
2
5
1

Explicație

Începând cu minutul $1$ distribuţiile în cele $4$ săli va fi următoarea:

0 4 0 0
0 4 1 0
0 4 1 1
1 4 1 1
1 5 1 1
1 5 2 1...