Migrated from Lutece 1304 Infinity Set

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Little A likes infinite set very much, so he creates a infinite set.

First, two numbers (may same) was added into an empty set. Next, if numbers $x$ and $y$ are in this set, $x+y$ was added into this set.

Because of this set has infinite numbers, Little A wants to know he $k^{th}$ small number in this set.

Input

The first line contains two numbers $a,b (1 \le a,b \le 5000)$, indicating the numbers added into empty set.

The second line contains one number $n (1 \le n \le 10^5)$, indicating the numbers of queries.

Next $n$ lines each line contains one number $k(1 \le k \le 10^9)$, indicating the query.

Output

For each query output one line.

Each line contains one number, the $k^{th}$ small number in the set.

Samples

2 3
5
1
2
3
4
5

2
3
4
5
6

3 5
5
1
2
3
4
5

3
5
6
8
9

Resources

The 14th UESTC Programming Contest Preliminary