Fişierul intrare/ieşire:	expozitie2.in, expozitie2.out	Sursă	Lot Măgurele 2016 - Baraj 4 Seniori
Autor	Adrian Panaete	Adăugată de	Tatomir Alex •atatomir
Timp execuţie pe test	0.5 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Expozitie2

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 ≤ i ≤ 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 ≤ 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 ≤ i ≤ 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 expozitie2.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 expozitie2.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

• 1 ≤ N ≤ 1.000;
• 1 ≤ Q ≤ 1.000.000;
• 1≤ y ≤ 1000;
• 1≤ x[i] ≤ 100 pentru fiecare i cu 1 ≤ i ≤ N;
• 0 ≤ s ≤ N pentru fiecare întrebare;
• 1≤ t ≤ 1.000.000.000 pentru fiecare întrebare;

Exemplu

Cum se trimit solutii?