有名なプログラマーが奇術師としての腕を試しています。彼の得意な手品は次のようなものです。

非負整数 $n$ 個からなる配列 $a_1,a_2,\ldots,a_n$ が与えられると、彼は魔法の数 $b$ を素早く見つけます。非負整数 $b$ が配列の魔法の数であるとは、配列の各要素とこの数とのビット単位の排他的論理和を取ることで、配列が昇順に整列することをいいます。すなわち、

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

となります。ここで $\oplus$ はビット単位の排他的論理和です。

手品をより印象的にするため、奇術師は与えられた配列に対する魔法の数を示した後、次の操作を $q$ 回行います。観客に配列の要素を一つ変更してもらい、その後でもう一度魔法の数を示そうとします。プログラマーは奇術師としての技術を磨き上げており、毎回、可能な魔法の数のうち最小のものを観客に示します。変更後の配列に対する魔法の数が存在せず、手品が失敗することもあります。

初期配列、および各要素の変更後の配列に対して、最小の魔法の数を求めるか、そのような数が存在しないと判定するプログラムを作成してください。

注記

排他的論理和は記号 $\oplus$ で表される論理演算で、次の真理値表によって定義されます。

二つの非負整数 $x$ と $y$ のビット単位の排他的論理和を定義します。それぞれを二進法で表し、必要なら短い方の先頭にゼロを補って桁数を揃えます。二つの整数 $x$ と $y$ のビット単位の排他的論理和も $x\oplus y$ と表し、その二進表現の各桁が $x$ と $y$ の対応する桁の排他的論理和となる非負整数です。例えば、$5\oplus22=101_2\oplus10110_2=10011_2=19$ です。

このオリンピックで使用できるプログラミング言語のうち、Pascal では排他的論理和を表す演算子は xor で、その他の言語では ^ です。

入力

入力の1行目には、配列内の数の個数を表す整数 $n$ が与えられます（$1\le n\le10^6$）。

2行目には、配列の要素を表す $n$ 個の整数 $a_1,a_2,\ldots,a_n$ が与えられます（$0\le a_i<2^{30}$）。

3行目には、配列の要素を変更する回数を表す整数 $q$ が与えられます（$0\le q\le10^6$）。

続く $q$ 行には、それぞれ二つの整数 $p_i$ と $v_i$ が与えられます。$p_i$ は置き換える配列要素の番号（$1\le p_i\le n$）、$v_i$ はその要素の新しい値（$0\le v_i<2^{30}$）です。

出力

$\left(q+1\right)$ 個の整数 $b_0,b_1,\ldots,b_q$ を、1行に一つずつ出力してください。

$b_0$ は初期配列に対する最小の魔法の数です。そのような数が存在しない場合は $-1$ としてください。

$1$ から $q$ までの各 $i$ について、$b_i$ は最初の $i$ 回の変更後の配列に対する最小の魔法の数です。そのような数が存在しない場合は $-1$ としてください。

入出力例

入力 1

3
0 1 4
3
2 7
3 3
1 4

出力 1

0
2
-1
4

小課題