xor

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ţă

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=(a \cdot i_{k-1} + b) \ mod \ m$
$j_k=(a \cdot j_{k-1} + b) \ mod \ m$

Date de intrare

Fişierul de intrare xor.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 xor.out va conţine q linii. Pe linia k se va afișa elementul situat pe linia $i_k$ coloana $j_k$ a matricii.

Restricţii şi precizări

• Pentru 10% dintre teste 1 ≤ q ≤ 100, 1 ≤ m ≤ 100
• Pentru alte 10% dintre teste 1 ≤ q ≤ 100 000 , 1 ≤ m ≤ 1000
• Pentru alte 30% dintre teste 1 ≤ q ≤ 50, 1 ≤ m ≤ 30 000
• Pentru alte 50% dintre teste 1 ≤ q ≤ 100 000, $1 ≤ m ≤ 10^8$
• $0 ≤ i_1, j_1 < m$
• 1 ≤ a, b ≤ 9

Exemplu

xor.in

4 2 3 1 1 5

xor.out

2
7
0
1

Explicaţie

Avem q=4 întrebări.
Pentru $i_1=2, j_1=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