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: 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}
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 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.
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).
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 Q.
Date de ieşire
Fişierul de ieşire xp.out va conţine o singură linie pe care va fi afişată valoarea Rez.
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.
Exemple
xp.in
xp.out
Explicaţii
5 4 6 10 15
10
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.