Most Likely And

curly_braces Criterion 2022 Round 19
Limits 5s, 512 MB

Tashdid has a secret array of size nn. For each index of the array, he will randomly choose an integer between xx and yy (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 xx and yy remain same, only the size of the array nn changes.

Input

The first line contains two space-separated integers xx and yy.

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

Each of the next QQ lines contains one integer each, nin_i, the size of the array in the i’th query.

Constraints

0xy20000 \leq x \leq y \leq 2000

1Q1051 \leq Q \leq 10^5

1ni<2631 \leq n_i < 2^{63}

Output

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

Samples

InputOutput
1 4
3
1
2
3
4
0
0
InputOutput
5 7
3
1
2
3
7
6
4

Submit

Login to submit.

Statistics

30% Solution Ratio
EgorKulikovEarliest, 3w ago
EgorKulikovFastest, 1.0s
EgorKulikovLightest, 786 kB
mdshadeshShortest, 1427B
Toph uses cookies. By continuing you agree to our Cookie Policy.