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

Intr-o seara, Por Costel, cel mai vestit dintre porci, a iesit la plimbare. Mergea linistit pe trotuar cand langa el s-a declansat o pocnitoare. Ca orice porc, a avut reactia defensiva de a incepe sa guitaie disperat si sa fuga de-alungul trotuarului.

Într-o seară, Por Costel, cel mai vestit dintre porci, a ieşit la plimbare. Mergea liniştit pe trotuar când lângă el s-a declanşat o pocnitoare. Ca orice porc, a avut reacţia defensivă de a începe sa guiţăie disperat şi să fugă de-alungul trotuarului.

Desi miscarea lui Por Costel de-alungul trotuarului pare aleatoare, la o inspectie amanuntita observam o anumita regula. Daca consideram strada divizata in pozitii indexate de la <tex>0</tex> la <tex>N-1</tex> iar la momentul <tex>i</tex> Por Costel se afla la pozitia <tex>X</tex>, la momentul <tex>i+1</tex> Por Costel se va afla la pozitia <tex>(X^2^ </tex><tex> + A)</tex> <tex>mod</tex> <tex>N</tex>.

Deşi mişcarea lui Por Costel de-alungul trotuarului pare aleatoare, la o inspecţie amănunţită observăm o anumită regulă. Sa consideram strada divizată în poziţii indexate de la <tex>0</tex> la <tex>N-1</tex>. Por Costel se află la momentul <tex>1</tex> în poziţia <tex>X_1</tex>. Dacă la momentul <tex>i</tex>, Por Costel se află la poziţia <tex>X</tex>, la momentul <tex>i+1</tex> Por Costel se va afla la poziţia <tex>(i*X + A)</tex> <tex>mod</tex> <tex>N</tex>.

Pentru a fi pregatiti de situatia in care Por Costel sare panicat in mijlocul strazii (Doamne fereste !), fanii lui va implora sa puteti raspunde in fiecare la moment la intrebari de genul: “In ce pozitie se afla acum Por Costel ?” Query-urile vor fi la fel de aleatoare ca si miscarea lui Por Costel. Voua vi se va da query-ul initial iar celelalte query-uri le generati utilizand formula: <tex>(i*X + A)</tex> <tex>mod</tex> <tex>(10^6</tex> <tex>+</tex> <tex>3)</tex>. unde <tex>i</tex> - indicele query-ului curent iar <tex>X</tex> - raspunsul la ultimul query iar <tex>a</tex> <tex>mod</tex> <tex>b</tex> este restul lui <tex>a</tex> la impartirea cu <tex>b</tex>.

Pentru a fi pregătiţi de situaţia în care Por Costel sare panicat în mijlocul străzii (Doamne fereşte !), fanii lui vă imploră sa puteţi spune în orice moment în ce poziţie se află el. Un query <tex>q</tex> semnifică întrebarea _"Pe ce poziţie se află Por Costel la momentul de timp q?"_ Query-urile vor fi la fel de aleatoare ca şi mişcarea lui Por Costel. Vouă vi se va da query-ul iniţial <tex>Q_1</tex> iar celelalte query-uri se generează astfel: dacă tocmai am răspuns la întrebarea <tex>Q_i</tex>, query-ul <tex>Q_i_+_1</tex> va fi <tex>(i*X_i + B)</tex> <tex>mod</tex> <tex>(10^7 + 3) + 1</tex> unde  <tex>X_i</tex> este răspunsul la query-ul <tex>i</tex>.

h2. Date de intrare

În fişierul de intrare $pocnitoare.in$ se va gasii pe prima linie <tex>T</tex>, numarul de teste, pe urmatoarele linii vor fi descrise testele astfel: prima linie va contine <tex>N</tex>, <tex>A</tex>, <tex>Q</tex> (nr. de query-uri), <tex>Q_1</tex>(query-ul initial), iar a doua linie va contine <tex>Q</tex> numere reprezentand query-urile.

În fişierul de intrare $pocnitoare.in$ se va găsii pe prima linie <tex>N</tex>, <tex>A</tex>, <tex>B</tex>, <tex>X_1</tex> (poziţia iniţială a lui Por Costel), <tex>Q</tex> (numărul de query-uri), <tex>Q_1</tex>(query-ul iniţial).

h2. Date de ieşire

În fişierul de ieşire $pocnitoare.out$ <tex>T</tex> linii fiecare cu cate <tex>Q_i</tex> <tex>(1</tex> &le; <tex>i</tex> &le; <tex>T)</tex> numere care reprezinta raspunsurile la fiecare din cele <tex>Q_i</tex> query-uri de la al <tex>i</tex>-lea test.

În fişierul de ieşire $pocnitoare.out$ se vor găsii <tex>Q</tex> linii, pe linia <tex>i</tex> aflându-se răspunsul la al <tex>i</tex>-lea query.

h2. Restricţii

* <tex>1</tex> &le; <tex>N</tex>, <tex>A</tex> &le; <tex>10^4^</tex>

* <tex>1</tex> &le; <tex>N</tex>, <tex>A</tex>, <tex>B</tex> &le; <tex>2 * 10^9</tex>
* <tex>0</tex> &le; <tex>X_1</tex> &le; <tex>N-1</tex>

* <tex>1</tex> &le; <tex>Q</tex> &le; <tex>10^5^</tex>

* <tex>1</tex> &le; <tex>Q_1</tex> &le; <tex>(10^7 + 3)</tex>
* <tex>a</tex> <tex>mod</tex> <tex>b</tex> reprezintă restul împărţirii lui <tex>a</tex> la <tex>b</tex>
* **Atenţie la limita de memorie!**

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

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

| 17 3 7 1 3 1
| 1
14
6

|
== include(page="template/taskfooter" task_id="pocnitoare") ==

10323