F. Volume
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Igor is an audiophile, and he is very sensitive to sound volume. He has speakers that output sound with a volume of $$$M$$$, but he wants to reduce the volume exactly to $$$V$$$. To achieve this, he has $$$N$$$ volume regulators. The special feature of these regulators is that they can only be set to values that are prime numbers or $$$1$$$. Initially, all the regulators are set to their maximum values, which are different for each regulator.

However, the values set on the regulators can be changed, and the overall volume will change proportionally. That is, if the value of one regulator is changed by a factor of $$$X$$$, while the values of the other regulators remain unchanged, the overall volume will also change by a factor of $$$X$$$, regardless of the values set on the other regulators. Of course, the regulator cannot be set to a value higher than its maximum.

Help Igor set the values on the regulators such that the volume from the speakers becomes equal to $$$V$$$.

Input

The first line of the input contains three positive integers $$$M$$$, $$$V$$$, and $$$N$$$ — the maximum volume, desired volume, and number of regulators ($$$0 \lt V \lt M \lt 10^9$$$; $$$N \leq 50$$$). The second line contains $$$N$$$ positive integers $$$m_i$$$ — the maximum values of the volume regulators ($$$2 \leq m_i \leq 10^9$$$).

Output

You need to output $$$N$$$ prime numbers — the values that need to be set on the regulators so that the volume becomes equal to $$$V$$$. The $$$i$$$-th number must not exceed the maximum value of the $$$i$$$-th regulator $$$m_i$$$.

If there are multiple solutions, output any.

If it is impossible to achieve a volume of $$$V$$$, output $$$-1$$$.

Examples
Input
50 15 3
5 2 3
Output
3 1 3
Input
35 21 2
7 5
Output
7 3
Input
21 12 4
3 3 5 7
Output
-1
Note

In the first example, by setting the values of the regulators to $$$3$$$, $$$1$$$, and $$$3$$$, the volume is $$$\frac{3}{5}\cdot\frac{1}{2}\cdot\frac{3}{3}=\frac{3}{10}$$$ of the maximum, which corresponds to the required volume of $$$15$$$.

In the second example, the volume is set to $$$\frac{3}{5}$$$ of the maximum $$$35$$$, which equals $$$21$$$.

In the third example, it is impossible to achieve a volume of $$$12$$$.