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ă KaTeX parse error: Unexpected character: '\' at position 23: …{\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

10

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

xp.in

3999999 9003 3333 30000 900330000

xp.out

594979072