== include(page="template/taskheader" task_id="secvente3") ==

Poveste şi cerinţă...

Fie {**A{~i~}**} un şir de numere naturale nenule definit astfel:
 
A{~1~} = {**a**}
A{~i~} = (A{~i-1~} × {**b**} ) modulo {**P**} , pentru orice i > 1
 
Astfel şirul A poate fi definit de trei numere constante cunoscute: {**a**}, {**b**} şi {**P**}.
 
h2. Cerinta
 
Pentru un şir cunoscut A să se raspundă la {**M**} întrebări ({**st**}, {**S**}) cu semnificaţia:
„Care este cel mai mare indice {**dr**} (≥st) astfel încât A ~st~ + A ~st+1~ + A ~st+2~ + … + A ~dr~ ≤ S ?”

h2. Date de intrare

Fişierul de intrare $secvente3.in$ ...

Fişierul de intrare $secvente3.in$ conţine pe prima linie numerele {**a**}, {**b**}, {**P**} şi {**M**} separate prin spaţiu. Următoarele {**M**} linii contin parametrii pentru fiecare întrebare {**st**} şi {**S**} separaţi prin spaţiu.

h2. Date de ieşire

În fişierul de ieşire $secvente3.out$ ...

În fişierul de ieşire $secvente3.out$ va conţine pe prima linie {**M**} numere: răspunsurile dr la întrebări în ordine, valori separate prin spaţiu.

h2. Restricţii

* $... ≤ ... ≤ ...$

* M ≤ 10^4^
* 1 ≤ st ≤ 10^6^
* 0 < dr ≤ 10^7^, pentru orice întrebare
* 1 < a < b < P ≤ 10^9^
* 0 < S ≤ 10^15^
* Pentru orice test numerele a, b şi P asigură că orice A{~i~} este nenul
* Pentru orice întrebare A{~st~} ≤ S
* Atentie la limita de memorie
* Atentie la folosirea long long (C++) sau int64 (Pascal)

h2. Exemplu
table(example). |_. secvente3.in |_. secvente3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2 3 7 2
2 15
4 8
| 4 5

|
h3. Explicaţie

...

A = (2, 6, 4, 5, 1, 3 …)
A{~2~} + A{~3~} + A{~4~} = 6 + 4 + 5 = 15 ≤ 15
A{~4~} + A{~5~} = 5 + 1 = 6 ≤ 8
dar A{~4~} + A{~5~} + A{~6~} = 5 + 1 +  3 = 9 e deja > 8
 
 
 

== include(page="template/taskfooter" task_id="secvente3") ==