Problem C
Xorcisten

Xorcisten Roxanne har en märklig förmåga, hon kan sortera listor väldigt snabbt. När hon ser en lista av heltal $a_1, a_2, \dots , a_ N$ så kan hon blixtsnabbt hitta ett heltal $X$ så att

där $\oplus $ betyder bitwise XOR¹. Allt hon behöver göra sen är att byta ut $a_ i$ mot $a_ i \oplus x$ och vips, så är listan sorterad!

Företag anlitar ofta Roxanne för att sortera deras jättelånga listor. Men en dag upptäckte Roxanne till sin besvikelse att hennes förmåga var borta. Din uppgift är att skriva ett program åt henne så att hon kan få behålla sitt jobb.

Du får givet en lista med icke-negativa heltal $a_1, \dots , a_ N$ och $Q$ stycken ändringar på formen $p_ i, v_ i$, som betyder att talet $a_{p_ i}$ ändras till $v_ i$. Du ska skriva ut $Q+1$ heltal $c_0, c_1, \dots , c_ Q$, där $c_ i$ är det minsta icke-negativa heltalet $X$ så att listan $a_1 \oplus X, \dots , a_ N \oplus X$ är sorterad, efter det att de första $i$ ändringarna har utförts. Om det inte finns något sånt tal $X$, skriv ut $-1$ istället.

Indata

Den första raden innehåller ett heltal $N$ ($1 \leq N \leq 10^6$) antalet tal i listan.

Den andra raden innehåller $N$ heltal $a_1, a_2, \dots , a_ N$ ($0 \leq a_ i < 2^{30})$, talen i listan.

Den tredje raden innehåller ett heltal $Q$ ($0 \leq Q \leq 10^6$), antalet ändringar.

De följande $Q$ raderna innehåller två heltal $p_ i$ ($1 \leq p_ i \leq N$), och $v_ i$ ($0 \leq v_ i < 2^{30}$) , vilket innebär att talet $a_{p_ i}$ ändras till $v_ i$.

Utdata

Du ska skriva ut $Q+1$ rader med heltal, talen $c_0, c_1, \dots , c_ Q$. $c_ i$ ska vara det minsta möjliga talet $x$ som sorterar listan efter det att ändringarna $1, 2, \dots , i$ har utförts (eller $-1$ om det inte finns något sådant tal $x$).

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper.

För att få poäng för en grupp så måste du klara alla testfall i gruppen.

3
0 1 4
3
2 7
3 3
1 4

0
2
-1
4