Programmer Rostislav got seriously interested in the Link/Cut Tree data structure, which is based on Splay trees. Specifically, he is now studying the $*expose*$ procedure.

Unfortunately, Rostislav is unable to understand the definition of this procedure, so he decided to ask programmer Serezha to help him. Serezha agreed to help if Rostislav solves a simple task (and if he doesn't, then why would he need Splay trees anyway?)

Given integers $*l*$, $*r*$ and $*k*$, you need to print all powers of number $*k*$ within range from $*l*$ to $*r*$ inclusive. However, Rostislav doesn't want to spent time doing this, as he got interested in playing a network game called Agar with Gleb. Help him!

Input

The first line of the input contains three space-separated integers $*l*$, $*r*$ and $*k*$ ($1 ≤ *l* ≤ *r* ≤ 10^{18}$, $2 ≤ *k* ≤ 10^{9}$).

Output

Print all powers of number $*k*$, that lie within range from $*l*$ to $*r*$ in the increasing order. If there are no such numbers, print "-1" (without the quotes).

Note

Note to the first sample: numbers $2^{0} = 1$, $2^{1} = 2$, $2^{2} = 4$, $2^{3} = 8$ lie within the specified range. The number $2^{4} = 16$ is greater then $10$, thus it shouldn't be printed.