Se consideră o matrice cu un număr infinit de linii și coloane indexate începând cu 0.
Pe prima linie matricea conține șirul numerelor naturale (0, 1, 2, 3 …).
Pe fiecare linie începând cu linia a doua pe poziția j matricea conține suma xor a elementelor situate pe linia anterioara de la poziția 0 până la poziția j.

Cerința

Se cere să se răspundă la q întrebări de forma “Pentru i și j date, să se determine numărul situat pe linia i coloana j a matricei”. Pentru a genera cele q întrebări vor fi cunoscute următoarele valori: \( i_1, j_1, a, b, m \).
\( i_1, j_1\) reprezintă valorile pentru prima întrebare. Următoarele întrebări \( i_k, j_k \) vor fi generate una din alta folosind următoarea regulă:

\( {i}_{k} = \left (a* {i}_{k-1} +b \right) \text{ mod } m \)
\( {j}_{k} = \left (a* {j}_{k-1} +b \right) \text{ mod } m \)

Date de intrare

Fișierul de intrare xor1.in conține pe prima linie numerele naturale \( q, i_1, j_1, a, b, m \) separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire xor1.out va conține q linii. Pe linia k se va afișa elementul situat pe linia \(i_k\) coloana \(j_k\) a matricei.

Restricții și precizări

• Pentru 10% dintre teste 1 ≤ q ≤ 100, 1 ≤ m ≤ 100
• Pentru alte 10% dintre teste 1 ≤ q ≤ 100000, 1 ≤ m ≤ 1000
• Pentru alte 30% dintre teste 1 ≤ q ≤ 50, 1 ≤ m ≤ 30000
• Pentru alte 50% dintre teste 1 ≤ q ≤ 100000, 1 ≤ m ≤ 108
• \( 0≤ {i}_{1} , {j}_{1} < m \)
• 1 ≤ a,b ≤ 9

Exemplu:

xor1.in

4 2 3 1 1 5

xor1.out

2
7
0
1

Explicație

Avem q=4 întrebări.

Pentru i1=2, j1=3, a=1, b=1, m=5 se obțin întrebările: (2,3), (3,4), (4,0), (0,1)

Matricea este:

0 1 2 3 4 5 6 …
0 1 3 0 4 1 7 …
0 1 2 2 6 7 0 …
0 1 3 1 7 0 0 …
0 1 2 3 4 4 4 …
…

Se observă că pe pozițiile corespunzătoare întrebărilor avem valorile 2, 7, 0 și 1.