Fişierul intrare/ieşire:	sir4.in, sir4.out	Sursă	Concursul National Urmasii lui Moisil 2011 - Clasa a 9-a
Autor	Paul Diac	Adăugată de	Andrici Cezar •andrici_cezar
Timp execuţie pe test	0.3 sec	Limită de memorie	5120 kbytes
Scorul tău	N/A	Dificultate	2/5

Vezi solutiile trimise | Statistici

Sir4

Fie şirul X_i definit de următoarele variabile de iniţializare: (X₀, A, B, M) astfel:

• X₀ este primul element al şirului
• X_i = (A * X_i-1 + B) % M, pentru orice i ≥ 1 (x % y reprezintă restul împărţirii întregi a lui x la y)

Răspundeţi la Q întrebări de forma: Fiind dată poziţia P_i a unui element din şir, să se determine valoarea acestuia, X_Pi.
Date variabilele de iniţializare X₀, A, B, M, determinaţi răspunsul pentru fiecare dintre cele Q întrebări.

Date de intrare

Programul citeşte date din fişierul sir4.in. Pe prima linie se găsesc numerele naturale X₀, A, B, M şi Q separate prin câte un spaţiu. Pe fiecare din următoarele Q linii se află în ordine, câte unul dintre numerele P₁,P₂,...P_Q, reprezentând poziţii ale unor termeni din şir.

Date de ieşire

Programul scrie pe prima linie din fişierul sir4.out, Q numere reprezentând răspunsurile, în ordine, la întrebările date. Numerele vor fi separate prin câte un spaţiu. După ultimul număr afişaţi caracterul de sfârşit de linie.

Restricţii

• 1 ≤ M ≤ 2 * 10⁶
• M este număr prim
• 1 ≤ X₀, A, B < M
• Q ≤ 10³
• 0 ≤ P_i < 10¹⁰⁰⁰⁰

Exemplu

Explicaţie

Primii 5 termeni ai şirului X sunt: 7, 10, 2, 8 şi 15.

Cum se trimit solutii?