407561: GYM102829 H Zorro's Revenge

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Zorro's Revengetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Zorro is angry at Erik (see Xorro the Xorman from the previous contest) for making a mockery of him with the creation of Xorro. The original swashbuckler decides to teach Erik a lesson by making him solve a problem of his own making, or to face the wrath of his blade. Zorro despises bitwise operations, but he is quite the number theory connoisseur. He gives Erik three positive integers $$$N$$$, $$$K$$$, and $$$X$$$, and asks the inferior swordsman to tell him if it is possible to sum exactly $$$K$$$ integer powers of $$$X$$$ to $$$N$$$. Can you save Erik from a gruesome fate (he is quite bad at number theory problems)?

Input

The first and only line of input contains three space separated integers $$$N$$$ ($$$1 \leq N \leq 10^{18}$$$), $$$K$$$ ($$$1 \leq K \leq 2 \cdot 10^5$$$), and $$$X$$$ ($$$2 \leq X \leq 9$$$) as described above.

Output

If it is NOT possible to construct such a sum of $$$K$$$ integer powers of $$$X$$$, output a single line containing "NO" (all caps, without quotes).

If it is possible, output "YES" (all caps, without quotes) on the first line of output. The second line of output should contain $$$K$$$ space-separated integers that are all integer powers of $$$X$$$ that in total sum to $$$N$$$. It is required that the outputted list is lexicographically minimized when printed out in descending order.

ExamplesInput
9 4 2
Output
YES
4 2 2 1 
Input
25 26 7
Output
NO

加入题单

上一题 下一题 算法标签: