piezisa

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$.

Date de intrare

Prima linie conține 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$ și $r_i$.

Date de ieșire

Se vor afișa q linii. Pe linia i, se va afla răspunsul la al i-lea plan.

Restricții

• 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 $0 ≤ i < n$
• $0 ≤ l_i ≤ r_i < n$, pentru oricare $0 ≤ i < q$

Subtask 1 (10 puncte)

• $1 ≤ n, q ≤ 500$

Subtask 2 (15 puncte)

• $1 ≤ n, q ≤ 3 \ 000$

Subtask 3 (5 puncte)

• $v_i < 4$, pentru oricare 0 ≤ i < n

Subtask 4 (40 puncte)

• $1 ≤ n ≤ 100 \ 000$

Subtask 5 (30 puncte)

• Nu există alte restricții

Exemplul 1

stdin

6
2 0 3 3 2 2
4
5 5
1 1
0 1
2 2

stdout

2
1
5
2

Explicație

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].

Exemplul 2

stdin

10
5 7 3 6 1 2 5 2 5 4
3
7 9
5 8
1 5

stdout

8
4
-1

Explicație

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$.