Fraction

During his first days in the mental ward, Berlaga pretended to be the viceroy of India. After giving it some thought, he decided it was risky. They could put him on an elephant and make him steer the beast through the streets. He opted for a change of story. He has not decided yet what his next persona will be. Meanwhile, he is enjoying his favorite pastime: playing Solitaire.

Every now and then, he begins to wonder: what portion of the games does he win? Solitaire itself provides the answer with only two decimal places, and Berlaga loves precision and sometimes calculates the proportion himself. The answer can be either a terminating or a repeating fraction, depending on the proportion itself and on the base of the numeral system used. That is right, mad accountants can use any positional numeral system they want, not only decimal. For instance, in the decimal system, $1/3$ is an infinite repeating fraction, and $4/10$ is a terminating fraction, however, in the ternary numeral system, everything is the other way around: $1/3$ is a terminating fraction "$0.1$", and $4/10$ is an infinite recurring fraction "$0.101210121012\ldots$".

Naturally, like all accountants, he does not like infinite fractions and prefers to calculate the proportion of his wins only when he is absolutely sure that it will be a terminating fraction. To do this, he needs to play a few more games.

Help Berlaga find the minimal number of games to be played additionally. The total number of played games must not be greater than $M$.

The first line of the input file contains three numbers: $B$, the base of the numeral system, $M$, the maximum allowed number of games, and $N$, the number of queries ($2 \le B \le 5 \cdot 10^6$, $1 \le M \le 10^{18}$, $1 \le N \le 10^5$).

The next $N$ lines describe the queries. Each line contains a single integer $a_i$, the number of games already played by Berlaga ($1 \le a_i \le M$).

The output file must contain $N$ lines, with an answer to the corresponding query in each line. Each answer must be an integer $A$, the number of games to be played additionally to ensure that the proportion of wins is a terminating fraction ($A \ge 0$). If the total number of games in this case is greater than $M$, print $-1$ as the answer.