P5623 [Celeste-A] Sever the Skyline

> The abandoned city is full of mechanisms and traps, and tonight, we will. > —Sever the skyline of this city.

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.

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.

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.)**

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