==Include(page="template/taskheader" task_id="reg")==
 
==Include(page="template/raw")==
 
Reg
 
 
 
Algostorm a inceput sa programeze satelitii intergalactici intr-un limbaj de programare denumit SuperP++ . Un program in SuperP++ consta dintr-o serie de instructiuni (numele acestor instructiuni sunt niste numere intregi) care trebuiesc executate in ordine. Pentru a fi executata, o instructiune trebuie citita din registri (acestia sunt in numar de K si fiecare registru poate retine cel mult o instructiune la un moment dat). Daca o instructiune nu exista in registri, aceasta trebuie incarcata inainte de a fi executata. O instructiune poate fi incarcata intr-un registru gol sau intr-un registru folosit caz in care instructiunea curenta este stearsa din registru (pentru eliberarea acestuia). Odata stearsa, o instructiune nu mai poate fi incarcata in nici un registru si la intalnirea ei in executarea programului acesta se intrerupe.
 
h2. Cerinta
 
Algostorm a scris un program compus din N instructiuni. Stiind numarul de registri, K , aflati care este numarul maxim de instructiuni din programul lui Algostorm care pot fi executate pana la intreruperea lui, respectand regulile de incarcare si citire.
 
h2. Date de Intrare
 
In fisierul reg.in se afla pe prima linie un numar T reprezentand numarul de teste care vor urma. Pe urmatoarele T linii se afla cate 5 numere: A , B , C , N , K . Programul lui Algostorm va fi descris de urmatoarele relatii ( Xi fiind instructiunea cu numarul i , i=1..N )
 
X1=1, Xi=(Xi-1 * A + B * i) mod C pentru i=2..N
 
h2. Date de Iesire
 
Fisierul de iesire reg.out va contine T linii: pentru fiecare test se va afisa pe cate o linie numarul maxim de instructiuni din programul lui Algostorm care pot fi executate utilizand exact K registri.
 
h2. Restrictii si precizari
 
. 1 <= N <= 2.000.000
 
. 1 <= T <= 10
 
. 1 <= A, B, C, K <= 500.000
 
. C este mereu prim
 
. suma numarului de instructiuni ale tuturor programelor dintr-un fisier de intrare nu va depasi 4.000.000
 
. Pentru 70% din fisierele de intrare N <= 400.000
 
. Instructiunile se vor executa in ordine, de la 1 catre N
 
. In timpul concursului s-a impus o limita de memorie de 7MB pentru segmentul de date si 1MB pentru stiva.
 
h2. Exemplu
 
 
|reg.in |reg.out |
 
|2 |3 |
|1 1 7 5 1 |6 |
|2 3 5 8 2 | |

==Include(page="template/taskheader" task_id="reg")==
 
 
Algostorm a inceput sa programeze satelitii intergalactici intr-un limbaj de programare denumit SuperP++ . Un program in SuperP++ consta dintr-o serie de instructiuni (numele acestor instructiuni sunt niste numere intregi) care trebuiesc executate in ordine. Pentru a fi executata, o instructiune trebuie citita din registri (acestia sunt in numar de $K$ si fiecare registru poate retine cel mult o instructiune la un moment dat). Daca o instructiune nu exista in registri, aceasta trebuie incarcata inainte de a fi executata. O instructiune poate fi incarcata intr-un registru gol sau intr-un registru folosit caz in care instructiunea curenta este stearsa din registru (pentru eliberarea acestuia). Odata stearsa, o instructiune nu mai poate fi incarcata in nici un registru si la intalnirea ei in executarea programului acesta se intrerupe.
 
h2. Cerinta
 
Algostorm a scris un program compus din $N$ instructiuni. Stiind numarul de registri, $K$, aflati care este numarul maxim de instructiuni din programul lui Algostorm care pot fi executate pana la intreruperea lui, respectand regulile de incarcare si citire.
 
h2. Date de intrare
 
In fisierul $reg.in$ se afla pe prima linie un numar $T$ reprezentand numarul de teste care vor urma. Pe urmatoarele $T$ linii se afla cate $5$ numere: $A$, $B$, $C$, $N$, $K$. Programul lui Algostorm va fi descris de urmatoarele relatii ({$X{~i~}$} fiind instructiunea cu numarul $i$, {$i = 1..N$})
 
$X{~1~} = 1$, $X{~i~} = (X{~i-1~} * A + B * i)$ mod $C$ pentru $i = 2..N$
 
h2. Date de iesire
 
Fisierul de iesire $reg.out$ va contine $T$ linii: pentru fiecare test se va afisa pe cate o linie numarul maxim de instructiuni din programul lui Algostorm care pot fi executate utilizand exact $K$ registri.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 2 000 000$
* $1 ≤ T ≤ 10$
* $1 ≤ A, B, C, K ≤ 500 000$
* C este mereu prim
* Suma numarului de instructiuni ale tuturor programelor dintr-un fisier de intrare nu va depasi $4 000 000$
* Pentru $70%$ din fisierele de intrare $N ≤ 400 000$
* Instructiunile se vor executa in ordine, de la $1$ catre $N$
 
h2. Exemplu
 
table(example). |_. reg.in |_. reg.out |
| 2
1 1 7 5 1
2 3 5 8 2
| 3
6 |
 
==Include(page="template/taskfooter" task_id="reg")==

==Include(page="template/taskfooter" task_id="reg")==

712