Problem: 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 ≤ 1018, 2 ≤ k ≤ 109).

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 20 = 1, 21 = 2, 22 = 4, 23 = 8 lie within the specified range. The number 24 = 16 is greater then 10, thus it shouldn't be printed.

Solution (in JAVA):

Solution:
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void solve() {
        long l = IO.readLong();
        long r = IO.readLong();
        long k = IO.readLong();

        boolean flag = false;
        if (l == 1) {
            IO.print("1 ");
            flag = true;
        }
        long a = k;
        while (a <= r && a % k == 0) {
            if (a >= l) {
                IO.print(a + " ");
                flag = true;
            }
            a *= k;
        }

        if (!flag) {
            IO.println("-1");
        }
    }

    // Input/Output ================================
    public static class IO {

        private static Scanner scanner;
        private static PrintWriter writer;

        public static void setUp(InputStream in, OutputStream out) {
            scanner = new Scanner(new java.io.BufferedInputStream(in));
            writer = new PrintWriter(out);
        }

        public static boolean isEmpty() {
            return !scanner.hasNext();
        }

        public static boolean hasNextLine() {
            return scanner.hasNextLine();
        }

        public static String readLine() {
            String line;
            try {
                line = scanner.nextLine();
            }
            catch (Exception e) {
                line = null;
            }
            return line;
        }

        public static String readString() {
            return scanner.next();
        }

        public static int readInt() {
            return scanner.nextInt();
        }

        public static int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int index = 0; index < n; ++index) {
                a[index] = readInt();
            }
            return a;
        }

        public static Pair<Integer, Integer>[] readIntArrayWithIndexes(int n) {
            Pair<Integer, Integer>[] a = new Pair[n];
            for (int index = 0; index < n; ++index) {
                a[index] = new Pair<>(index, readInt());
            }
            return a;
        }

        public static double readDouble() {
            return scanner.nextDouble();
        }

        public static float readFloat() {
            return scanner.nextFloat();
        }

        public static long readLong() {
            return scanner.nextLong();
        }

        public static char readChar() {
            return scanner.findInLine("[^\\s]").charAt(0);
        }

        public static void print(Object o) {
            writer.print(o);
            writer.flush();
        }

        public static void println(Object o) {
            writer.println(o);
            writer.flush();
        }
    }

    // Algorithms ================================

    private static class Algo {

        private static int binSearch(int[] array, int n, int lo, int hi) {
            if (lo > hi) {
                return lo;
            }

            int mid = lo + (hi - lo) / 2;
            int cmp = (int) java.lang.Math.signum(n - array[mid]);
            if (cmp < 0) {
                return binSearch(array, n, lo, mid - 1);
            }
            else if (cmp == 0) {
                return mid;
            }
            else {
                return binSearch(array, n, mid + 1, hi);
            }
        }

        private static void permutations(int n) {
            int[] p = new int[n];
            for (int index = 0; index < n; ++index) {
                p[index] = index + 1;
            }

            while (true) {
                IO.println(Arrays.toString(p));

                int k = n - 1;
                while (k > 0) {
                    if (p[k] < p[k - 1]) {
                        k--;
                    }
                    else {
                        break;
                    }
                }
                if (k == 0) {
                    break;
                }
                int j = n - 1;
                while (p[j] < p[k - 1]) {
                    j--;
                }

                int t = p[j];
                p[j] = p[k - 1];
                p[k - 1] = t;

                int i = 0;
                while (k + i < n - 1 - i) {
                    t = p[k + i];
                    p[k + i] = p[n - i - 1];
                    p[n - i - 1] = t;
                    i++;
                }
            }
        }

        private static boolean isPrime(int number) {
            if (number <= 1) {
                return false;
            }
            if (number <= 3) {
                return true;
            }
            if (number % 2 == 0 || number % 3 == 0) {
                return false;
            }
            int i = 5;
            while (i * i <= number) {
                if (number % i == 0 || number % (i + 2) == 0) {
                    return false;
                }
                i += 6;
            }
            return true;
        }

        private static boolean isPrimeOrOne(int number) {
            return number == 1 || isPrime(number);
        }

        private static boolean isPalindrome(int number) {
            int n = number;
            int reverse = 0;
            while (n > 0) {
                reverse *= 10;
                reverse += (n % 10);
                n /= 10;
            }
            return reverse == number;
        }

        public static int gcd(int a, int b) {
            while (b != 0) {
                int tmp = a % b;
                a = b;
                b = tmp;
            }
            return a;
        }
    }

    private static class Math2 {

        static long c(int n, int k) {
            if (n == 0 && k == 0) {
                return 1;
            }
            int d = 1000;
            int l = 1000000007;
            long[][] c = new long[d + 1][d + 1];
            for (int i = 1; i <= d; ++i) {
                for (int j = 0; j <= i; ++j) {
                    if (i == j || j == 0) {
                        c[i][j] = 1;
                    }
                    else {
                        c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % l;
                    }
                }
            }
            return c[n][k];
        }
    }

    static class Pair<K, V> {
        K key;
        V value;

        Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        IO.setUp(System.in, System.out);
        /*
        try {
            IO.setUp(new FileInputStream("encode.in"), new FileOutputStream("encode.out"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
            return;
        }
        */
        solve();
    }
}