Most Likely And

Tashdid has a secret array of size $n$. For each index of the array, he will randomly choose an integer between $x$ and $y$ (both inclusive) and set the value of that index to that random integer.

After creating the arrays, Tashdid gave you a task. You have to guess the bitwise-and value of the whole array.

Now as you don't know the secret array, you will make a guess based on probability. You will guess a number so that the probability of your answer being correct is the most. If there exists more than one number with the same probability then you will guess the highest number with that probability. What is your guess?

You have to answer several queries. In all the queries the values of $x$ and $y$ remain same, only the size of the array $n$ changes.

Input

The first line contains two space-separated integers $x$ and $y$.

The next line contains a single integer $Q$, the number of queries.

Each of the next $Q$ lines contains one integer each, $n_i$, the size of the array in the i’th query.

Constraints

$0 \leq x \leq y \leq 2000$

$1 \leq Q \leq 10^5$

$1 \leq n_i < 2^{63}$

Output

For each of the queries, print an integer in a line, your guess for that query.

Samples

Input	Output
1 4 3 1 2 3	4 0 0

Input	Output
5 7 3 1 2 3	7 6 4