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

Fie Ai un şir de numere naturale nenule definit astfel:

Fie A ~i~ un şir de numere naturale nenule definit astfel:

A1 = a
Ai = (Ai-1 × b) modulo P, pentru orice i > 1

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 Ast + Ast+1 + Ast+2 + … + Adr ≤ S ?”

„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

* 1 < a < b < P ≤ 10^9^
* 0 < S ≤ 10^15^
* 0 < dr ≤ 10^7^, pentru orice întrebare

* Pentru orice test numerele a, b şi P asigură că orice Ai este nenul
* Pentru orice întrebare Ast ≤ S

* 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)