一位知名程式設計師嘗試成為魔術師。他最拿手的魔術如下。
對於給定的、由 $n$ 個非負整數 $a_1,a_2,\ldots,a_n$ 組成的陣列，他會迅速選出一個魔法數 $b$。若將陣列的每個元素與非負整數 $b$ 進行位元互斥或運算後，陣列變為已排序的陣列，就稱 $b$ 為這個陣列的魔法數。換句話說，
$$(a_1\oplus b)\le(a_2\oplus b)\le\cdots\le(a_n\oplus b),$$
其中 $\oplus$ 表示位元互斥或運算。
為了讓魔術更加精彩，魔術師在展示給定陣列的魔法數之後，會進行 $q$ 次以下操作：他請觀眾修改陣列中的一個元素，然後再次嘗試展示一個魔法數。這位程式設計師的魔術技藝已經十分精湛，每次都會向觀眾展示最小的可能魔法數。有時魔術會失敗，因為無法為修改後的陣列找到魔法數。
請編寫程式，對給定的初始陣列以及每次元素修改後的陣列，計算最小的魔法數，或判定這樣的數不存在。
說明
互斥或是一種邏輯運算，以符號 $\oplus$ 表示，其真值表如下：
| $x$ | $y$ | $x\oplus y$ |
|---|---|---|
| $0$ | $0$ | $0$ |
| $0$ | $1$ | $1$ |
| $1$ | $0$ | $1$ |
| $1$ | $1$ | $0$ |
以下定義兩個非負整數 $x$ 和 $y$ 的位元互斥或。將 $x$ 和 $y$ 各自寫成二進位表示，必要時在較短的數前面補零，使兩者長度相同。兩個整數 $x$ 和 $y$ 的位元互斥或也記作 $x\oplus y$，它是一個非負整數，其二進位表示中的每一位，都是 $x$ 和 $y$ 對應位的互斥或。例如，$5\oplus22=101_2\oplus10110_2=10011_2=19$。
在本次奧林匹亞競賽提供的程式語言中，Pascal 使用運算子 xor 表示互斥或，其他程式語言則使用運算子 ^。
輸入格式
輸入的第一行包含一個整數 $n$，表示陣列中的數的個數（$1\le n\le10^6$）。
第二行包含 $n$ 個整數 $a_1,a_2,\ldots,a_n$，表示陣列的元素（$0\le a_i<2^{30}$）。
第三行包含一個整數 $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}$）。
輸出格式
輸出應包含 $q+1$ 個整數 $b_0,b_1,\ldots,b_q$，每行一個。
$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
子任務
| 子任務 | 分數 | $n$ 的限制 | $q$ 的限制 | $a_i,v_i$ 的限制 | 所需子任務 | 比賽期間提供的結果 |
|---|---|---|---|---|---|---|
| $1$ | $30$ | $1\le n\le500$ | $0\le q\le500$ | $0\le a_i,v_i<2^9$ | 各測試點的結果 | |
| $2$ | $29$ | $1\le n\le1000$ | $0\le q\le1000$ | $0\le a_i,v_i<2^{30}$ | $1$ | 各測試點的結果 |
| $3$ | $21$ | $1\le n\le10^5$ | $0\le q\le10^5$ | $0\le a_i,v_i<2^{30}$ | $1,2$ | 分數 |
| $4$ | $20$ | $1\le n\le10^6$ | $0\le q\le10^6$ | $0\le a_i,v_i<2^{30}$ | $1$–$3$ | 分數 |