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:

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

 
* $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. Restricţii

$1 ≤ N ≤ 4 000 000$
$2 ≤ P ≤1 000 000 000$
$2 ≤ Q ≤ 1 000 000 000$
$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$.

* $1 ≤ N ≤ 4 000 000$
* $2 ≤ P ≤1 000 000 000$
* $2 ≤ Q ≤ 1 000 000 000$
* $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$.

h2. Exemplu