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


-----Examples-----
Input
1 10 2

Output
1 2 4 8 
Input
2 4 5

Output
-1


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

Difficulty: interview

Starter code:

Solutions:
l, r, n = map(int, input().split())
a = n
n = 1
cnt = 0
while n <= r:
    if n >= l:
        cnt += 1
        print(n, end=' ')
    n *= a
if cnt == 0:
    print(-1)

l, r, k = map(int, input().split())
curr = 1
cnt = 0
while (curr <= r):
    if (curr >= l):
        print(curr, end = ' ')
        cnt += 1
    curr *= k
if (cnt == 0):
    print(-1)

#!/usr/bin/env python3

try:
    while True:
        l, r, k = list(map(int, input().split()))
        x = 1
        ls = [ ]
        while x <= r:
            if x >= l:
                ls.append(x)
            x *= k
        if ls:
            print(' '.join(map(str, ls)))
        else:
            print(-1)

except EOFError:
    pass


#!/bin/python
import collections
import random
import sys
try:
    from tqdm import tqdm
except:
    def tqdm(iterable):
        return iterable


__taskname = ''
if __taskname:
    sys.stdin = open(__taskname + '.in')
    sys.stdout = open(__taskname + '.out', 'w')

l, r, k = list(map(int, input().split()))
a, x, i = [], 1, 0
while x <= r:
    if x >= l:
        a.append(x)
    x *= k
    i += 1
print(*(a if a else [-1]))


l, r, k = map(int, input().split())

s = 1

while s < l:
	s *= k

ans = []
while s <= r:
	ans.append(s)
	s *= k

if ans:
	print(' '.join(str(v) for v in ans))
else:
	print(-1)

l, r, k = [int(x) for x in input().split()]
ans = []
a = 1
while a <= r:
    if a >= l:
        ans.append(a)
    a *= k

if ans:
    for num in ans:
        print(num, end = ' ')
else:
    print(-1)


l, r, k = list(map(int, input().split()))

n = 1
numbers = []

while n <= r:
    if n >= l:
        numbers.append(n)

    n *= k

if len(numbers) > 0:
    print(' '.join(map(str, numbers)))
else:
    print('-1')


read = lambda: map(int, input().split())
l, r, k = read()
cur = 1
flag = 0
while cur <= r:
    if cur >= l:
        flag = 1
        print(cur, end = ' ')
    cur *= k
if flag == 0: print(-1)
    


l, r, k = map(int, input().split())

curk = 1

while curk < l:
    curk *= k

ans = 0

while curk <= r:
    ans += 1
    print(curk, end=' ')
    curk *= k

if not ans:
    print(-1)
else:
    print()


l, r, k = map(int, input().split())
_k = int(k)
k = 1
ans = 0
ok = 0
while(k <= r) :
    if(k >= l) : 
        print(k, end = ' ')
        ok = 1
    k *= _k
if(ok == 0) :
    print(-1)

l, r, k = map(int, input().split())
ans = []
nowa = 1;
while (nowa <= r):
    if (nowa >= l):
        ans.append(nowa)
    nowa *= k
if (len(ans) == 0):
    print(-1)
else:
    print(*ans)

l, r, k = map(int, input().split())
i, f = 1, False
while i <= r:
    if i >= l:
        f = True
        print(i, end=' ')
    i *= k
if not f:
    print('-1')

l, r, k = list(map(int, input().split()))


t = 1
rez = []
for i in range(80):
	if l <= t <= r:
		rez.append(t)
	t *= k
if rez:
	print(*rez)
else:
	print(-1)


l, r, k = list(map(int, input().split()))
n = 1
ans = []
while n <= r:
    if l <= n <= r:
        ans.append(n)
    n *= k
if ans:
    print(*ans)
else:
    print(-1)


l, r, k = list(map(int, input().split()))
a = list()
x = 1
while x <= r:
	if l <= x <= r:
		a.append(x)
	x *= k
if len(a) == 0:
	print(-1)
else:
	print(' '.join(map(str, a)))


l, r, k = map(int, input().split())
flag = 1
n = 1
while (n <= r) :
    if (n >= l) :
        print(n, end = " ")
        flag = 0
    n *= k
if (flag == 1) :
    print(-1)

l, r, k = map(int, input().split())
cur = 1
while cur < l:
    cur *= k
f = False
while cur <= r:
    f = True
    print(cur,end=' ')
    cur *= k
if not f:
    print(-1)


l, r, n = [int(x) for x in input().split()]

f = 1
count = 0
while f <= r:
    if f >= l:
        print(f, end=" ")
        count += 1

    f *= n

if count == 0:
    print(-1)


a,b,c=map(int,input().split())

val=1
flag=0

while val<=b:
    if val>=a:
        flag=1
        print(val,end=" ")
    val=val*c

if flag==0:
    print(-1)


l, r, k = map(int, input().split())
st = 1
fl = False
while (st <= r):
    if (st >= l and st <= r):
        print(st, end = " ")
        fl = True
        st *= k
    else:
        st *= k
if not fl:
    print(-1)


l, r, k = list(map(int, input().split()))
x = 1
while x < l:
    x *= k
a = []
while x <= r:
    a.append(x)
    x *= k

print(-1 if not a else ' '.join(list(map(str, a))))


l, r, k = [int(x) for x in input().split()]

x = 1

correct = False
while x <= r:
    if x >= l:
        print(x, end=" ")
        correct = True
    x *= k

if not correct:
    print("-1")
else:
    print("")


l, r, k = map(int, input().split())
cur = 1
flag = True
while cur <= r:
    if cur >= l and cur <= r:
        print(cur, end=" ")
        flag = False
    cur *= k
if flag:
    print(-1)

l,r,k=[int(x) for x in input().split()]
ans=False
x=1
while x<=r:
    if l<=x:
        print(x, end=' ')
        ans=True
    x*=k
if not ans:
    print(-1)


#In the name of Allah

from sys import stdin, stdout
input = stdin.readline

l, r, k = list(map(int, input().split()))
res = []
n = 1
while n <= r:
        if n >= l:
                res.append(str(n))
                
        n *= k
if len(res):
        stdout.write(" ".join(res))
else:
        stdout.write("-1"
                     )