Problem 1350: 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 \leq i \leq N$ avem:

$A[i] = ((A[i-1] + P - 1) \ \textit{\textbf{XOR}} \ (B[i-1] + 1) \ \textit{\textbf{mod}} \ P$

$B[i] = ((A[i-1] + P - 1) \ \textit{\textbf{OR}} \ (B[i-1] + 1) \ \textit{\textbf{mod}} \ P$

Pentru $1 \leq i \leq 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:

$\textit{\textbf{XOR}}$ : sau-exclusiv pe biţi
$\textit{\textbf{OR}}$ : sau pe biţi
$\textit{\textbf{AND}}$ : şi pe biţi
$F \textit{\textbf{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]$ ) $\textit{\textbf{mod}} \ G$ .

Mai exact, $Prod[i] = (val[1] \cdot val[2] \cdot \ldots \cdot val[i-1] \cdot val[i+1] \cdot \ldots \cdot val[N]) \ \textit{\textbf{mod}} \ Q$ .

Cerinţă

Să se calculeze valoarea $Rez = Prod[1] \ XOR \ Prod[2] \ \textit{\textbf{XOR}} \ \ldots \ \textit{\textbf{XOR}} \ Prod[N]$ (adică $\textit{\textbf{XOR}} \$ între toate cele $N$ valori $Prod[i]$ , $1 \leq i \leq N$ ).

Date de intrare

Fişierul de intrare xp.in conţine pe prima (şi singura) linie $5$ numere naturale separate prin câte un spaţiu, reprezentând, în ordine, valorile $N, A[1], B[1], P$ şi $Q$ .

Date de ieşire

Fişierul de ieşire xp.out va conţine valoarea $Rez$ .

Restricții și precizări

$1 \leq N \leq 4 \ 000 \ 000$
$2 \leq P \leq 1 \ 000 \ 000 \ 000$
$2 \leq Q \leq 1 \ 000 \ 000 \ 000$
$0 \leq A[1], B[1] \leq P - 1$
Pentru $30\%$ dintre teste vom avea $N \leq 10 \ 000$
Pentru alte $20\%$ dintre teste vom avea $10 \ 001 \leq N \leq 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$

Exemplul 1

xp.in

5 4 6 10 15

xp.out

Explicație

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 \ \textit{\textbf{XOR}} \ 5 \ \textit{\textbf{XOR}} \ 5 \ \textit{\textbf{XOR}} \ 5 \ \textit{\textbf{XOR}} \ 5 = 10$ .

Exemplul 2