== 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, veţi construi voi şirul $V$ pe baza unui şir auxiliar $S$ de lungime $M$, cu elemente numerotate de la $0$ la $M-1$. Elementul de pe fiecare poziţie $i, 0 ≤ i < N$, din vectorul $V$ va fi calculat cu următoarea formulă:
== code(cpp) |
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 Y$ se afla după procedeul:
== code(cpp) |
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$
* $1 ≤ M ≤ 1000, N ≤ M * M$
* Pentru $20$ de puncte $1 ≤ N , Q ≤ 100$
* Pentru alte $20$ de puncte $1 ≤ N ≤ 1000 si 1 ≤ Q ≤ 100$
* Pentru alte $15$ de puncte $1 ≤ N ≤ 10000 si 1 ≤ Q ≤ 100$
* Elemente şirului $V$ încap pe $32$ de biti
* $1 &le; S[i] < 2^29$
* $0 &le; A,B,C,D &le; 10^3$
* O subsecvenţă este un subşir de elemente care apar pe poziţii consecutive în şirul iniţial
* Operaţia $xor$ reprezintă operaţia de disjuncţie exclusivă realizată pe biţii operanzilor. În Pascal, operatorul corespunzător este $xor$, iar în C/C++ acest operator este $^$. De exemplu, $20 xor 14 = 26$.
* 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

table(example). |_. aiacuxor.in |_. aiacuxor.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. aiacuxor.in |_. aiacuxor.out |_. explicatie |
| 4 4 4
10 8 10 8
1 1 9 8 5 3
| 4
5
0
1
| Sirul V de lungime N = 4 : 0 3 2 5
Cele 4 intrebari sunt:
1 1
2 2
2 3
3 4
Vom explica în detaliu răspunsul pentru ultima întrebare:
Secvenţele din şirul V cu lungimea cuprinsă între [3, 4] sunt:
(0, 3, 2) (între poziţiile 0 şi 2);
(3, 2, 5) (între poziţiile 1 şi 3);
(0, 3, 2, 5) (între poziţiile 0 şi 3).
f(0, 2) = 0 xor 3 xor 2 = 1
f(1, 3) = 3 xor 2 xor 5 = 4
f(0, 3) = 0 xor 3 xor 2 xor 5 = 4
Răspunsul pentru ultima intrebare este: 1 xor 4 xor 4 = 1
|
| 10 10 4
2 8 9 1
6 9 9 6 2 9
| 28
5
23
5
22
22
23
11
0
0
| Se obtine şirul V:
0 11 13 6 14 5 7 16 19 10
Se obţin întrebările:
6 9
1 9
4 4
1 6
6 8
3 5
8 9
6 7
4 7
5 9
|

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

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