407394: GYM102783 G Hyper Chocolate Cubes

Felix is going trick or treating this year! Last year, he was not able to get enough chocolate, and the year before, he got too much, and he had to throw some away. This year, after carefully planning out exactly how much chocolate he is going eat for the next month, he decides that he wants exactly $$$x$$$ cubes of chocolate.

However, once Halloween arrived, Felix forgot all about his precise amount of chocolate that he wanted and he ran down the street and grabbed a piece of chocolate from every house along the way. Felix lives on a very weird street with $$$100$$$ houses, and turns out, while the first four houses simply give out respectively 1 chocolate cube, $$$w$$$ chocolate cubes in a line, $$$w^2$$$ chocolate cubes in a square, and $$$w^3$$$ chocolate cubes in a $$$w \times w \times w$$$ cube, from the 5th house onwards, things actually continue! By the time Felix hits the $$$100^{th}$$$ house, he is getting an $$$100$$$-dimensional hypercube with sidelength $$$w$$$, and hence getting $$$w^{100}$$$ chocolate cubes.

Now, this does not really matter to Felix, since he just wants the right amount of chocolate. Turns out, his mother knew about his endeavors and decided to buy him some chocolate that she claims is the exact amount of chocolate that Felix wants. Felix however does not believe his mother and with his $$$n$$$ hypercubes of chocolate and his trusty balance scale, he decides to see if he can determine if his mother really did get him the right amount of chocolate. Help Felix find out if he can determine the exact amount of chocolate cubes in the package his mother gave him to help out his task!

Given that Felix does not want to break his cubes of chocolate, he will only use it in the shape that it was given to him, determine if there is a way to arrange some subset of his cubes of weight $$$1, w, w^2, \ldots, w^{100}$$$ can be put on either side of the balance scale, with his mother's chocolate on one side such that the scale balances.

The first line of the input will contain integers $$$n$$$ ($$$1 \le n \le 20$$$) and $$$w$$$ ($$$2 \le w \le 10$$$), the number of packages Felix wants to test and the side length of the hypercubes, respectively.

The next $$$n$$$ lines will each contain a single integer $$$x_i$$$ ($$$1 \leq x_i \leq 10^9$$$), the hidden weight of the $$$i$$$-th package.

Output $$$n$$$ lines, each with YES if it is possible to balance the scale, and NO if it is not possible to balance the scale.

4 5
25
26
29
32

YES
YES
YES
NO

For the first weight of $$$25$$$ is on one side of the balance, you can simply place the square of cubes (of weight $$$5^2$$$) on the other side of the balance. If the weight is $$$26$$$ is on one side, you can place the square of cubes (weight $$$5^2$$$) and a single cube (weight $$$1$$$) on the other side of the balance. If the weight is $$$29$$$ on one side, then you can place a single cube (weight $$$1$$$) on the same side as that weight and then place the square of cubes (weight $$$5^2$$$) and the line of cubes (weight $$$5$$$) on the other side and it will be balanced.