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.
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>(i*X + A)</tex> <tex>mod</tex> <tex>N</tex>.
Desi miscarea lui Por Costel de-alungul trotuarului pare aleatoare, la o inspectie amanuntita observam o anumita regula. Sa consideram strada divizata in pozitii indexate de la <tex>0</tex> la <tex>N-1</tex>. Por Costel se afla initial in pozitia <tex>X_1</tex>. Daca 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>(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 orice 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 se genereaza astfel: daca tocmai am raspuns la intrebarea <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)</tex> unde <tex>i</tex> - indicele ultimului query, <tex>X_i</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 pregatiti de situatia in care Por Costel sare panicat in mijlocul strazii (Doamne fereste !), fanii lui va implora sa puteti spune in orice moment in ce pozitie se afla el. Un query <tex>q</tex> semnifica intrebarea _"Pe ce pozitie se afla Por Costel la momentul de timp q?"_ Query-urile vor fi la fel de aleatoare ca si miscarea lui Por Costel. Voua vi se va da query-ul initial <tex>Q_1</tex> iar celelalte query-uri se genereaza astfel: daca tocmai am raspuns la intrebarea <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 raspunsul la query-ul <tex>i</tex>.
h2. Date de intrare
În fişierul de intrare $pocnitoare.in$ se va gasii pe prima linie <tex>N</tex>, <tex>A</tex>, <tex>X_0</tex> (pozitia initiala a lui Por Costel), <tex>Q</tex> (numarul de query-uri), <tex>Q_1</tex>(query-ul initial).
În fişierul de intrare $pocnitoare.in$ se va gasii pe prima linie <tex>N</tex>, <tex>A</tex>, <tex>B</tex>, <tex>X_1</tex> (pozitia initiala a lui Por Costel), <tex>Q</tex> (numarul de query-uri), <tex>Q_1</tex>(query-ul initial).
h2. Date de ieşire
În fişierul de ieşire $pocnitoare.out$ se vor gasii <tex>Q</tex> linii, pe fiecare linia <tex>i</tex> aflanduse raspunsul la al <tex>i</tex>-lea query.
În fişierul de ieşire $pocnitoare.out$ se vor gasii <tex>Q</tex> linii, pe linia <tex>i</tex> aflandu-se raspunsul la al <tex>i</tex>-lea query.
h2. Restricţii
* <tex>1</tex> ≤ <tex>N</tex>, <tex>A</tex>, <tex>B</tex>, <tex>X_0</tex> ≤ <tex>2 * 10^9</tex>
* <tex>1</tex> ≤ <tex>N</tex>, <tex>A</tex>, <tex>B</tex>, <tex>X_1</tex> ≤ <tex>2 * 10^9</tex>
* <tex>1</tex> ≤ <tex>Q</tex> ≤ <tex>10^5^</tex>
* <tex>0</tex> ≤ <tex>Q_1</tex> ≤ <tex>(10^7 + 2)</tex>
* **Atentie!** pozitiile sunt indexate de la 0, pe cand queryurile de la 1!
* <tex>1</tex> ≤ <tex>Q_1</tex> ≤ <tex>(10^7 + 3)</tex>
* <tex>a</tex> <tex>mod</tex> <tex>b</tex> reprezinta restul impartirii lui <tex>a</tex> la <tex>b</tex>
* **Atentie la limita de memorie!**
h2. Exemplu
