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!

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

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

提交代码