== include(page="template/taskheader" task_id="aiacuxor") ==
Poveste şi cerinţă...
Bulănel nu a fost atent la ora de informatică şi drept urmare a înţeles prost tema primită. Fiindcă nu e în stare să o facă, vă cere vouă ajutorul.
Bulănel are un şir $V$ cu $N$ elemente. Fie $f(i,j)$= suma xor a elementelor subsecvenţei determinate de poziţiile cuprinse între $[i,j]$, $i≤j$ ( $V(i) xor V(i+1) xor … xor V(j)$ ). Bulănel e curios să afle care este suma xor a valorilor returnate de funcţia **f** pentru toate subsecvenţele din şirul V cu lungimea cuprinsă între $[X, Y] (X≤Y)$. Deoarece e curios Bulănel vă pune $Q$ astfel de întrebări.
Având în vedere că Bulănel stă prost cu cititul, vă dă la dispoziţie un şir auxiliar $S$ de lungime $M$, indexat de la $0$ la $M-1$, cu ajutorul căruia vă veţi construi şirul $V$. Elementul de pe fiecare poziţie $i, 0 ≤ i < N$, din vectorul $V$ va fi calculat cu următoarea formulă:
$_V[i] = (S[i / M] xor S[i mod M]) + i_$, unde $x / y$ reprezintă câtul împărţirii lui $x$ la $y$, $x$ $mod$ $y$ reprezintă restul lui $x$ la împărţirea cu $y$, şi $x xor y$ reprezintă rezultatul operaţiei $xor$ (sau exclusiv pe biţi) dintre $x$ şi $y$.
De asemenea şi întrebările se generează în felul următor: ştiind prima intrebare $X Y$ următoarele perechi $X_nou, Y_nou$ se afla după formulele:
$_X_nou=(X * A + Y * B) mod N + 1_$
$_Y_nou=(Y * C + (Z mod N) * D) mod N + 1_, (unde Z reprezintă răspunsul ultimei întrebări iar A, B, C, D sunt nişte constante date în fişierul de intrare)$
$_daca X_nou > Y_nou:_$
$_interschimba X_nou, Y_nou_$
$_X = X_nou_$
$_Y = Y_nou_$
h2. Cerinta
Cunoscând $N$, numărul de elemente din şirul $V$, $Q$ numărul de întrebări şi şirul $S$ cu ajutorul căruia vă veţi construi şirul $V$ Bulănel vă roagă să îi răspundeţi corect la toate cele $Q$ întrebări.
h2. Date de intrare
Fişierul de intrare $aiacuxor.in$ ...
Fişierul de intrare $aiacuxor.in$ conţine pe prima linie un număr natural $N$, care reprezintă lungimea şirului $V$, urmat de $Q$, care reprezintă numarul de întrebări, şi $M$, lungimea şirului auxiliar $S$. Pe următoarea linie se află $M$ numere, reprezentând şirul $S$ cu elemente numerotate de la $0$ la $M-1$. Pe a treia linie se afla $X şi Y$, care reprezintă lungimea minimă, respectiv lungimea maximă, ale secvenţelor luate în calcul pentru prima întrebare iar în continuare urmează în ordine $A, B, C, D$, constantele cu ajutorul cărora vă veţi construi următoarele întrebări, de la a doua până la $a Q-a$.
h2. Date de ieşire
În fişierul de ieşire $aiacuxor.out$ ...
În fişierul de ieşire $aiacuxor.out$ contine $Q$ linii, fiecare conţinând răspunsul corespunzator celei de $a i-a$ întrebare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ X ≤ Y ≤ N ≤ 1000000$
* $1 ≤ Q ≤ 1000000$
* Pentru $20$ de puncte $1 ≤ N , Q ≤ 100$
* Pentru alte $20$ de puncte $1 ≤ N ≤ 1000 si 1 ≤ Q ≤ 100$
* Pentru alte $20$ de puncte $1 ≤ N ≤ 10000 si 1 ≤ Q ≤ 100$
* Elemente şirului $V$ încap pe $32$ de biti
* $1 ≤ S[i] < 2^29$
* $0 ≤ A,B,C,D ≤ 10^3$
* O subsecvenţă este un subşir de elemente care apar pe poziţii consecutive în şirul iniţial
* xor reprezintă operatorul binar „sau exclusiv” xor (Pascal) / ^ (C/C++)
* Modul de generare al şirului, respectiv a întrebărilor, se datorează doar faptului că Bulănel citeşte foarte greu.
* Problema va fi evaluată pe teste în valoare de $90$ de puncte
* Se vor acorda $10$ puncte din oficiu
h2. Exemplu
