== include(page="template/taskheader" task_id="xp") ==

Se consideră $3$ şiruri, numite $A, B$ şi $val$, fiecare dintre ele având câte $N$ elemente naturale nenule. Elementele din cadrul şirurilor sunt indexate de la $1$ la $N$. Cunoscându-se $A{~1~}, B{~1~}$ şi o valoare naturală nenulă $P$, regula după care se calculează elementele şirurilor este următoarea:
Pentru $2 ≤ i ≤ N$ avem:

Se consideră $3$ şiruri, numite $A$, $B$ şi $val$, fiecare dintre ele având câte $N$ elemente naturale nenule. Elementele din cadrul şirurilor sunt indexate de la $1$ la $N$. Cunoscându-se $A{~1~}$, $B{~1~}$ şi o valoare naturală nenulă $P$, regula după care se calculează elementele şirurilor este următoarea:

* $A{~i~} = ((A{~i-1~} + P - 1) XOR (B{~i-1~} + 1)) mod P$
* $B{~i~} = ((A{~i-1~} + P - 1) OR (B{~i-1~} + 1)) mod P$

* Pentru $2 ≤ i ≤ N$ avem:
** $A{~i~} = ((A{~i-1~} + P - 1) XOR (B{~i-1~} + 1)) mod P$
** $B{~i~} = ((A{~i-1~} + P - 1) OR (B{~i-1~} + 1)) mod P$.
* Pentru $1 ≤ i ≤ N$ avem:
** $val{~i~} = max{1, ((i mod P) XOR (((A{~i~} + 1) AND (B{~i~} + 1)) mod P)) mod P}$.

Pentru $1 ≤ i ≤ N$ avem:
 
* $val{~i~} = max{1, ((i mod P) XOR (((A{~i~} + 1) AND (B{~i~} + 1)) mod P)) mod P}$
 
Operaţiile utilizate în formulele de mai sus au următoare semnificaţie:

$F mod G$ reprezintă restul împărţirii lui $F$ la $G$. Definim $Prod{~i~}$ ca fiind egal cu: (produsul tuturor elementelor şirului $val$, cu excepţia lui $val{~i~}) mod Q$. Mai exact, $Prod{~i~} = (val{~1~}·val{~2~}·...·val{~i-1~}·val{~i+1~}·...·val{~N~}) mod Q$. Operaţiile utilizate în formulele de mai sus au următoarea semnificaţie:

* $XOR$ : $sau-exclusiv$ pe biţi
* $OR$ : $sau$ pe biţi
* $AND$ : $şi$ pe biţi

$F mod G$ reprezintă restul împărţirii lui $F$ la $G$
Definim $Prod{~i~}$ ca fiind egal cu: (produsul tuturor elementelor şirului $val$, cu excepţia lui $val{~i~}) mod Q$.
Mai exact, $Prod{~i~} = (val{~1~}·val{~2~}·...·val{~i-1~}·val{~i+1~}·...·val{~N~}) mod Q$.
 

h2. Cerinţă

Să se calculeze valoarea $Rez = Prod{~1~} XOR Prod{~2~} XOR ... XOR Prod{~N~}$ (adică $XOR$ între toate cele $N$ valori $Prod{~i~}, 1≤i≤N$).

Să se calculeze valoarea $Rez = Prod{~1~} XOR Prod{~2~} XOR ... XOR Prod{~N~}$ (adică $XOR$ între toate cele $N$ valori $Prod{~i~}, 1 ≤ i ≤ N$).

h2. Date de intrare

h2. Restricţii
* $1 ≤ N ≤ 4 000 000$

* $2 ≤ P ≤1 000 000 000$

* $2 ≤ P ≤ 1 000 000 000$

* $2 ≤ Q ≤ 1 000 000 000$

* $0 ≤ A{~1~}, B{~1~}; P-1$

* $0 ≤ A{~1~}, B{~1~} ≤ P-1$

* Pentru $30%$ dintre teste vom avea $N ≤ 10 000$.

* Pentru alte $20%$ dintre teste vom avea $10 001 ≤ N ≤ 200 000.
* Problema nu urmăreşte găsirea vreunei proprietăţi speciale a relaţiilor de generare a elementelor şirurilor $A, B$ şi $val$.

* Pentru alte $20%$ dintre teste vom avea $10 001 ≤ N ≤ 200 000$.
* Problema nu urmăreşte găsirea vreunei proprietăţi speciale a relaţiilor de generare a elementelor şirurilor $A$, $B$ şi $val$.

h2. Exemplu

h3. Explicaţie pentru primul exemplu:

Se obţin următoarele şiruri A, B şi val:
$A{~1~}=4, B{~1~}=6, val{~1~}=4$
$A{~2~}=0, B{~2~}=5, val{~2~}=2$
$A{~3~}=5, B{~3~}=5, val{~3~}=5$
$A{~4~}=8, B{~4~}=4, val{~4~}=5$
$A{~5~}=0, B{~5~}=1, val{~5~}=5$
Se obţin următoarele valori pentru şirul $Prod $(în ordine, de la $1$ la $5$): $10, 5, 5, 5, 5$.

Se obţin următoarele şiruri $A$, $B$ şi $val$:
 
* $A{~1~}=4, B{~1~}=6, val{~1~}=4$
* $A{~2~}=0, B{~2~}=5, val{~2~}=2$
* $A{~3~}=5, B{~3~}=5, val{~3~}=5$
* $A{~4~}=8, B{~4~}=4, val{~4~}=5$
* $A{~5~}=0, B{~5~}=1, val{~5~}=5$
 
Se obţin următoarele valori pentru şirul $Prod$ (în ordine, de la $1$ la $5$): $10, 5, 5, 5, 5$.
 

Obţinem $Rez = 10 XOR 5 XOR 5 XOR 5 XOR 5 = 10$.
== include(page="template/taskfooter" task_id="xp") ==

4750