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

Pentagonul a primit un nou mesaj de la unul din agenţii săi secreţi. Mesajul este reprezentat de un şir de N numere naturale. Pentru a putea verifica autenticitatea mesajului, agenţii trebuie să ataşeze la mesaj o cheie de verificare, a cărei metodă de obţinere este cunoscută doar de către membrii agenţiei. Comisia InfoOltenia a reuşit să afle această metodă: având la dispoziţie 2 numere M şi K cunoscute, pentru fiecare subsecvenţă de K numere din şir se calculează restul împărţirii produsului lor la M, iar cheia de verificare va fi suma xor a acestor resturi.

Pentagonul a primit un nou mesaj de la unul din agenţii săi secreţi. Mesajul este reprezentat de un şir de $N$ numere naturale. Pentru a putea verifica autenticitatea mesajului, agenţii trebuie să ataşeze la mesaj o cheie de verificare, a cărei metodă de obţinere este cunoscută doar de către membrii agenţiei. Comisia InfoOltenia a reuşit să afle această metodă: având la dispoziţie $2$ numere $M$ şi $K$ cunoscute, pentru fiecare subsecvenţă de $K$ numere din şir se calculează restul împărţirii produsului lor la $M$, iar cheia de verificare va fi suma xor a acestor resturi.

h2. Cerinţă

Cunoscându-se M, K şi şirul de numere pe care comisia vrea să îl trimită Pentagonului, determinaţi cheia de verificare corespunzătoare şirului de numere, care trebuie ataşată mesajului.

Cunoscându-se $M, K$ şi şirul de numere pe care comisia vrea să îl trimită Pentagonului, determinaţi cheia de verificare corespunzătoare şirului de numere, care trebuie ataşată mesajului.

h2. Date de intrare

Prima linie a fişierului $cia.in$ va conţine numerele N, T, K şi M.
A doua linie va conţine elementele unui şir A, de T numere naturale.
A treia linie va conţine elementele unui şir B, de T numere naturale.
Fie V şirul de N numere care trebuie transmis, pentru fiecare i(0≤i≤N-1) V[i] se va calcula după formula:
V[i] = (A[i mod T] xor B[i div T]) mod M. Şirurile V, A, B sunt indexate de la 0, a mod b reprezintă restul
împărţirii lui a la b, a div b reprezintă câtul împărţirii lui a la b, iar a xor b, suma xor a numerelor a şi b.

Prima linie a fişierului $cia.in$ va conţine numerele $N, T, K$ şi $M$. A doua linie va conţine elementele unui şir $A$, de $T$ numere naturale. A treia linie va conţine elementele unui şir $B$, de $T$ numere naturale. Fie $V$ şirul de $N$ numere care trebuie transmis, pentru fiecare $i (0 ≤ i ≤ N - 1) V[i]$ se va calcula după formula: $V[i] = (A[i mod T] xor B[i div T]) mod M$. Şirurile $V, A, B$ sunt indexate de la $0, a mod b$ reprezintă restul împărţirii lui $a$ la $b$, $a div b$ reprezintă câtul împărţirii lui $a$ la $b$, iar $a xor b$, suma xor a numerelor $a$ şi $b$.

h2. Date de ieşire

h2. Restricţii

* T ≤ 70.000
* 1 ≤ K ≤ N ≤ 10^7^
* 1 ≤ M < 2^30^
* Elementele şirurilor A şi B sunt numere naturale ce pot fi reprezentate pe 32 de biţi cu semn.
* pentru 5% din punctaj: 1 ≤ N*K ≤ 10^7^
* pentru alte 15% din punctaj 1 ≤ N ≤ 200.000, iar M este prim
* pentru alte 15% din punctaj 1 ≤ M ≤ 10^7^ , M este prim
* pentru alte 25% din punctaj 1 ≤ N ≤ 200.000

* $T ≤ 70.000$
* $1 ≤ K ≤ N ≤ 10^7^$
* $1 ≤ M < 2^30^$
* Elementele şirurilor $A$ şi $B$ sunt numere naturale în intervalul $[0,2^31^)$.
* pentru $5%$ din punctaj: $1 ≤ N*K ≤ 10^7^$
* pentru alte $15%$ din punctaj $1 ≤ N ≤ 200.000$, iar $M$ este prim
* pentru alte $15%$ din punctaj $1 ≤ M ≤ 10^7^$ , $M$ este prim
* pentru alte $25%$ din punctaj $1 ≤ N ≤ 200.000$

* prin subsecvenţă se înţelege un subşir de elemente plasate pe poziţii consecutive.

* suma xor a P numere a1, a2, a3 ... aP este egala cu a1 xor a2 xor a3 xor ... xor aP.

* suma xor a $P$ numere $a ~1~, a ~2~, a ~3~ ... a ~P~$ este egala cu $a{~1~} xor a{~2~} xor a{~3~} xor ... xor a{~P~}.$

h2. Exemplu

h3. Explicaţie

Şirul ce trebuie transmis este (6, 1, 4, 6).
Avem 2 subsecvenţe de lungime 3. Ambele au produsul elementelor 24, deci ambele au restul împărţirii produsului elementelor la 15 egal cu 9.
Suma xor a numerelor 9 şi 9 este 9 xor 9 = 0.

Şirul ce trebuie transmis este $(6, 1, 4, 6)$.
Avem $2$ subsecvenţe de lungime $3$. Ambele au produsul elementelor $24$, deci ambele au restul împărţirii produsului elementelor la $15$ egal cu $9$.
Suma xor a numerelor $9$ şi $9$ este $9 xor 9 = 0$.

== include(page="template/taskfooter" task_id="cia") ==