Программист Ростислав серьёзно увлёкся структурой данных Link/Cut Tree, которая основана на Splay-деревьях. В частности, сейчас он изучает процедуру expose.
К сожалению, понять определение этой процедуры Ростислав не в состоянии, и поэтому он решил обратиться за помощью к программисту Серёже. Тот согласился помочь, только если Ростислав решит простую задачу (а если не решит, то зачем ему Splay-деревья?)
По заданным l, r и k необходимо вывести все степени числа k в промежутке от l до r, включая границы. Однако Ростиславу не хочется решать эту задачу самостоятельно, ведь он увлекся сетевой игрой в Agar с Глебом. Помогите ему!
Выходные данные
Выведите все степени числа k, лежащие в промежутке от l до r, в порядке возрастания. Если таких чисел не существует, выведите "-1" (без кавычек).
Примечание
Пояснение к первому примеру: 1 = 20, 2 = 21, 4 = 22, 8 = 23. 16 = 24, что больше чем 10, следовательно не подходит.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 10 2
|
1 2 4 8
|
|
2
|
2 4 5
|
-1
|