I. Minimum XOR
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of length $$$n$$$, and you should answer $$$q$$$ queries of the following form:

— "$$$x$$$": Find the minimum value of $$$a_i \oplus a_j$$$ ($$$1 \le i \lt j \le n$$$) such that ($$$a_i \: \: | \: \: a_j \: \: | \: \: x \: = \: x$$$).

Note that $$$\oplus$$$ and $$$|$$$ denote the bitwise $$$XOR$$$ and the bitwise $$$OR$$$ operations, respectively.

Input

The first line of the input contains a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the length of the array $$$a$$$.

The second line of the input consists of $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

The third line of the input contains a single integer $$$q$$$ ($$$1 \le q \le 10^6$$$) — the number of queries.

Each of the following $$$q$$$ lines contains a single integer $$$x$$$ ($$$1 \le x \le 10^6$$$) — the description of the $$$i$$$-th query.

Output

Output $$$q$$$ lines, the $$$i$$$-th of which contains a single integer — the answer to the query, or $$$-1$$$ if there is no such pair that satisfies the conditions.

Example
Input
3
1 2 4
3
3
6
4
Output
3
6
-1