En känd programmerare provar rollen som illusionist. Hans paradnummer består av följande.

För en given array med $n$ icke-negativa heltal $a_1,a_2,\ldots,a_n$ hittar han snabbt ett magiskt tal $b$. Ett icke-negativt heltal $b$ kallas magiskt för arrayen om en bitvis exklusiv ELLER-operation med detta tal på varje element förvandlar arrayen till en sorterad array. Med andra ord,

$$(a_1\oplus b)\le (a_2\oplus b)\le\ldots\le(a_n\oplus b),$$

där $\oplus$ är bitvis exklusiv ELLER.

För att göra numret mer effektfullt utför illusionisten följande handling $q$ gånger efter att ha presenterat ett magiskt tal för den givna arrayen. Han ber åskådarna ändra ett av arrayens element och försöker sedan återigen presentera ett magiskt tal. Programmeraren har finslipat sina färdigheter som illusionist så mycket att han varje gång presenterar det minsta möjliga magiska talet. Ibland misslyckas numret, eftersom det inte går att hitta något magiskt tal för den resulterande arrayen.

Skriv ett program som beräknar det minsta magiska talet för den ursprungliga arrayen och efter varje ändring av ett element, eller avgör att något sådant tal inte finns.

Anmärkning

Exklusiv ELLER är en logisk operation som betecknas med $\oplus$ och definieras av följande sanningstabell:

Vi definierar bitvis exklusiv ELLER för två icke-negativa heltal $x$ och $y$. Skriv båda heltalen $x$ och $y$ i binär form och komplettera vid behov det kortare talet med inledande nollor så att de får samma längd. Bitvis exklusiv ELLER för de två heltalen $x$ och $y$, som också betecknas $x\oplus y$, är det icke-negativa heltal vars varje binära siffra är exklusiv ELLER av motsvarande siffror i $x$ och $y$. Till exempel är $5\oplus22=101_2\oplus10110_2=10011_2=19$.

Bland de programmeringsspråk som erbjuds på olympiaden används operatorn xor i Pascal för exklusiv ELLER, medan operatorn ^ används i de övriga programmeringsspråken.

Indata

Den första raden innehåller heltalet $n$, antalet tal i arrayen ($1\le n\le10^6$).

Den andra raden innehåller $n$ heltal $a_1,a_2,\ldots,a_n$, arrayens element ($0\le a_i<2^{30}$).

Den tredje raden innehåller heltalet $q$, antalet ändringar av ett element i arrayen ($0\le q\le10^6$).

Var och en av de följande $q$ raderna innehåller två heltal $p_i$ och $v_i$, där $p_i$ är indexet för det element som ska ersättas ($1\le p_i\le n$), och $v_i$ är elementets nya värde ($0\le v_i<2^{30}$).

Utdata

Utdata ska innehålla $q+1$ heltal $b_0,b_1,\ldots,b_q$, ett per rad.

Värdet $b_0$ är det minsta möjliga magiska talet för den ursprungliga arrayen, eller $-1$ om något sådant tal inte finns.

För $i$ från $1$ till $q$ är $b_i$ det minsta möjliga magiska talet för arrayen efter de första $i$ ändringarna, eller $-1$ om något sådant tal inte finns.

Exempel

Indata 1

3
0 1 4
3
2 7
3 3
1 4

Utdata 1

0
2
-1
4

Poängsättning