程序员 Rostislav 对基于 Splay 树的链接/剪切树数据结构非常感兴趣。具体来说,他现在正在研究曝光程序。
不幸的是,Rostislav 无法理解这个程序的定义,因此他决定请程序员 Serezha 来帮助他。如果 Rostislav 解决了一个简单的任务,Serezha 同意提供帮助(如果他没有解决,那么他为什么还需要 Splay 树呢?)
给定整数 l、r 和 k,您需要打印从 l 到 r 范围内的数字 k 的所有幂。然而,Rostislav 不想花时间这样做,因为他对与 Gleb 一起玩名为 Agar 的网络游戏感兴趣。帮助他!
输入
输入的第一行包含三个空格分隔的整数 l、r 和 k (1 ≤ l ≤ r ≤ 1018, 2 ≤ k ≤ 109)。
输出
按升序打印从 l 到 r 范围内的数字 k 的所有幂。如果没有这样的数字,则打印“-1”(不带引号)。
示例
输入 #1
1 10 2
输出 #1
1 2 4 8
输入 #2
2 4 5
输出 #2
-1
注意
第一个样本请注意:数字 20 = 1、21 = 2、22 = 4、23 = 8 位于指定范围内。数字 24 = 16 大于 10,因此不应打印它。