piezisa

Piezișă

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

Poveste şi cerinţă...

**Nota**: Din motive de capacitate a serverului InfoArena, multe modificari substantiale au fost facute testelor de evaluare. Astfel, punctajele obtinute in concurs pot diferi de cele obtinute aici.
 
Cunoscut pentru multe lucruri importante, cum ar fi metroul oraşului şi festivalul Nespus, oraşul Jluc găzduieşte încă un obiectiv turistic, totuşi mai puţin cunoscut decât cele menţionate anterior – Piezişă.
 
La prima vedere, Piezişă este doar o stradă, cu mai multe magazine de-a lungul ei. Mai exact, aceasta are $n$ magazine poziţionate de-a lungul ei, numerotate de la $0$ la $n − 1$. Totuşi, Piezişă este mai mult decât ceea ce pare: este un loc unde se creează amintiri. Magazinul $i$ are un numar asociat $v{~i~}$, care reprezintă calitatea amintirilor create în acel magazin.
 
Auzind de această stradă, Alex îşi doreşte să viziteze un interval continuu de magazine în seara aceasta. El are $q$ planuri de asemenea intervale, al $i$-lea fiind de forma $[l{~i~}, r{~i~}]$. Pentru a nu pierde timp, el doreşte să meargă pe Piezişă cu noua sa trotinetă electrică. Totuşi, Alex este superstiţios, şi este convins că dacă suma xor a valorilor $v{~i~}$ dintr-un interval vizitat nu ar fi $0$, atunci asta i-ar aduce ghinion. Aşadar, pentru fiecare plan, el doreşte să afle lungimea intervalului de lungime minimă care conţine magazinele din plan, şi care are suma xor $0$.
 
Formal, se dă un şir de $n$ valori intregi, şi $q$ intervale de forma $[l{~i~}, r{~i~}]$. Trebuie să calculaţi, pentru fiecare astfel de interval, lungimea intervalului de lungime minimă $[x, y]$, cu proprietatea că $x ≤ l{~i~} ≤ r{~i~} ≤ y$ şi pentru care $v{~x~} xor v{~x+1~} xor ... xor v{~y~} = 0$.

h2. Date de intrare

Fişierul de intrare $piezisa.in$ ...

Pe prima linie a fişierul de intrare $piezisa.in$ se va afla un singur număr natural, reprezentând valoarea lui $n$. A doua linie conţine $n$ numere întregi, reprezentând valorile $v{~0~}, v{~1~}, ... , v{~n−1~}$ ​. A treia linie conţine un singur număr natural, reprezentând valoarea lui $q$. Pe următoarele $q$ linii se află valorile corespunzătoare planurilor. Linia $i + 3$ conţine $2$ valori întregi, reprezentând $[l{~i~}, r{~i~}]$.

h2. Date de ieşire

În fişierul de ieşire $piezisa.out$ ...

În fişierul de ieşire $piezisa.out$ se vor afişa $q$ linii. Pe linia $i$, se va afla răspunsul la al $i$-lea plan.

h2. Restricţii

h2. Restricţii şi precizări

* $... ≤ ... ≤ ...$

* Operaţia xor reprezintă operaţia de sau exclusiv pe biţi. în $C/C++$, acest operator este $^$.
* Dacă pentru un plan, nu există niciun segment cu suma xor egala cu $0$, atunci răspunsul este $−1$.
* $1 ≤ n ≤ 500 000$.
* $1 ≤ q ≤ 500 000$.
* $0 ≤ v{~i~} ≤ 2^30^$, pentru oricare $1 ≤ i ≤ n$.
* $0 ≤ l{~i~} ≤ r{~i~} ≤ n$, pentru oricare $1 ≤ i ≤ q$.

h2. Exemplu

h2. Subtaskuri
 
table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $10$ | $1 ≤ n, q ≤ 500$   |
| $2$ | $15$ | $1 ≤ n, q ≤ 3 000$ |
| $3$ | $5$ | $v{~i~} < 4$, pentru oricare $1 &le; i &le; n$ |
| $4$ | $40$ | $1 &le; n &le; 100 000$ |
| $5$ | $30$ | Fără restricţii suplimentare |

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

h2. Exemple

...

table(example). |_. piezisa.in |_. piezisa.out |
| 6
  2 0 3 3 2 2
  4
  5 5
  1 1
  0 1
  2 2
| 2
  1
  5
  2
|
| 10
  5 7 3 6 1 2 5 2 5 4
  3
  7 9
  5 8
  1 5
| 8
  4
  -1
|
 
h3. Explicaţii
 
Pentru primul exemplu:
 
Primul plan doreşte să viziteze magazinul de pe poziţia $5$, care are valoarea $2$. Observăm că subsegmentul $[4, 5]$ (care conţine valorile $2, 2$) are suma xor $0$, aşadar el este cel mai mic subsegment cu xor $0$ care conţine $[5, 5]$. Răspunsul va fi, aşadar, $2$.
Al doilea plan conţine doar magazinul de pe poziţia $1$, care are valoarea $0$. Segmentul optim pentru acest plan este $[1, 1]$.
Al treilea plan conţine magazinele $0$ şi $1$, care au valorile $2$, $0$. Segmentul optim pentru acest plan este $[0, 4]$.
Al doilea plan conţine doar magazinul de pe poziţia $2$, care are valoarea $3$. Segmentul optim pentru acest plan este $[2, 3]$.
 
Pentru cel de-al doilea exemplu:
 
Pentru primul plan, unul dintre segmentele optime este $[2, 9]$, de lungime $8$.
Pentru al doilea plan, unul dintre segmentele optime este $[5, 8]$, de lungime $4$.
Pentru al treilea plan, nu există niciun subsegment valid, aşadar este afişat $−1$.

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