Background

Iris and Beryl are playing a number guessing game.

Problem Description

The game works as follows: given a positive integer $n$, Iris chooses a number $m$ from $S=\{1,2,...,n\}$.

Then, Iris must answer Beryl’s questions truthfully. Each question is of the form: “Is $m$ an element of set $A$?” where $A\subseteq S$.
If Iris answers “Yes”, then Beryl must give Iris $a$ yuan; otherwise, Beryl must give Iris $b$ yuan. (The testdata guarantees $a>b$.)

How much money does Beryl need to prepare at least, to be sure that she can determine the number in Iris’s mind?

Input Format

The first line contains two positive integers $a$ and $b$, and the number of test cases $t$.
The next $t$ lines each contain a given positive integer $n$, with the meaning as described above.

Output Format

Output $t$ lines. For each test case, output the minimum amount of money Beryl needs to prepare.

2 1 2
3
6

3
5

5 3 1
3

8

Hint

[Explanation for the 1st test case of Sample 1]

Beryl first asks about the set $\{1\}$. If the answer is “Yes”, then Iris’s number is confirmed to be $1$, and Beryl needs $2$ yuan. If the answer is “No”, then Beryl asks about the set $\{2\}$. Clearly, in the worst case she needs to spend another $2$ yuan, for a total of $3$ yuan, so the answer is $3$ yuan.

[Constraints]

Translated by ChatGPT 5