Description

Madeline arrived at an abandoned city. The city is full of mechanisms, and there is also a machine of unknown purpose emitting light signals outward.

With Madeline’s strong observation skills, she discovered that the light signals actually correspond to some dash order. After dashing in that order, she found that her dash trail formed the skyline of this abandoned city.

Many years later, when Madeline looked back on her mountain-climbing journey, she no longer remembered what the skyline of that city looked like. She only remembered that the sum of all building heights is $n$, and that each building’s height can be written as $p^iq^j$, where $p, q$ are prime numbers and $i, j \geq 0, i + j \geq 1$.

Madeline knows that the skyline of this city is aesthetically pleasing: there do not exist two buildings whose heights are in an integer multiple relationship (a multiple of 1 also counts). For example, if there is a building of height $2$, then there must not be a building of height $4$.

Because Madeline’s memory is quite vague, she may ask you multiple times to provide a valid skyline for a specific memory.

Input Format

The first line contains an integer $T$, indicating the number of queries from Madeline.

The next $T$ lines each contain three integers $n, p, q$, representing, respectively, the sum of building heights in this memory and the $p, q$ described in the statement.

Output Format

For each memory, output one line containing several integers separated by spaces, representing one valid skyline.

It is guaranteed that each test case has a solution. If there are multiple valid solutions, output any one.

Do not add extra spaces at the end of the line, otherwise you will get WA. (That is, no trailing spaces at the end of the line.)

3
15 2 3
10 2 5
416873881340965120 2 7

6 9
10
8507630225817856 19446011944726528 22224013651116032 12699436372066304 8293509467471872 4739148267126784 1354042362036224 3094953970368512 1768545125924864 32339110874054656 5279854836580352 1508529953308672 3448068464705536 3940649673949184 288230376151711744

Hint

For the first $30\%$ of the testdata, it is guaranteed that $n \leq 100$.

For another $20\%$ of the testdata, it is guaranteed that $p, q \leq 3$.

For $100\%$ of the testdata, it is guaranteed that $1 < n \leq 10^{18}$, $p, q \leq 40$, $p < q$, and $T \leq 10000$.

For the last $30\%$ of the testdata, bundled tests are used: you will score only if you pass all test points.

It is guaranteed that the testdata is generated as follows:

Uniformly randomly choose two primes $p, q$, randomly select several $p^iq^j$ and ensure they are not multiples of each other, take the sum of these $p^iq^j$ as $n$. If this data satisfies the requirements of the current test point, keep it; otherwise, regenerate.

For the last $30\%$ of the test points, $n$ is required to satisfy $n > 10^{17}$.

For some test points in the last $30\%$ of the test points, it is required to select at least $4$ such $p^iq^j$ to form $n$.

The format accepted by the SPJ is: no trailing spaces at the end of the line, and each output line ends with a newline.

If the format is incorrect, you may receive UKE.

Translated by ChatGPT 5