Fișierul intrare/ieșire	arondate.in, arondate.out	Sursă	ad-hoc
Autor	Victor Manz	Adăugată de	Victor Manz • vmanz
Timp de execuție pe test	0.8 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	2.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Arondate

Miaunel știe deja ce este un număr prim: un număr natural mai mare sau egal cu 2, care nu are alți divizori în afară de 1 și el însuși (nu are divizori proprii). În plus, el a rezolvat și problema ”arondat” de la olimpiada pe școală. Conform enunțului acesteia, numărul prim arondat numărului natural nenul N este acel număr prim P calculat în felul următor: dacă N este prim, atunci P=N; dacă N nu este prim, atunci numărul prim arondat lui N este egal cu numărul prim arondat sumei dintre cel mai mic și cel mai mare dintre divizorii proprii ai lui N. De exemplu, dacă N este 17, atunci numărul prim arondat lui N este 17. Dacă N este 26, atunci calculăm suma dintre cel mai mic divizor propriu al lui N și cel mai mare divizor propriu al lui N: 2+13=15; repetăm procedeul pentru 15 și obținem 3+5=8, apoi pentru 2+4=6 și 2+3=5, care e prim. Deci numărul prim arondat numerelor 5, 6, 8, 15 și 26 este 5.

Acum însă profesorul lui Miaunel îi propune o problemă ceva mai dificilă. Va trebui să răspundă la Q întrebări de forma ”care este numărul prim arondat lui N?”.

Întrebările corespund termenilor șirului x definit în felul următor:

x(1) = A
x(2) = B
x(n) = 5 + ( x(n-2) + C*x(n-1) ) % 999995

Date de intrare

Fișierul de intrare arondate.in va conține pe prima linie, separate prin câte un spațiu numerele Q, A, B și C.

Date de ieșire

În fișierul de ieșire arondate.out se vor afișa pe câte un rând separat răspunsurile la cele Q întrebări. Pe rândul i va fi scris răspunsul la întrebarea asociată celui de-al i-lea termen al șirului, x(i).

Restricții

• 3 ≤ Q ≤ 10 000 000
• 5 ≤ A ≤ 10 000
• 5 ≤ B ≤ 10 000
• 1 ≤ C ≤ 100

Exemplu

Explicație

Fișierul de ieșire conține răspunsurile la întrebările corespunzătoare primilor 4 termeni ai șirului. Aceștia sunt 5, 6, 22 și 55. Numărul prim arondat lui 5 este 5, numărul prim arondat lui 6 este 5, numărul prim arondat lui 22 este 13 (22 -> 13 = 2 + 11), iar numărul prim arondat lui 55 este 7 (55 -> 16 = 5 + 11 -> 10 = 2 + 8 -> 7 = 2 + 5).