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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.OutputStream;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedOutputStream;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            long l = in.nextLong(), r = in.nextLong();
            int k = in.nextInt();
            BigInt ans = new BigInt(1), L = new BigInt(l), R = new BigInt(r);
            boolean valid = false;
            for (int i = 0; i < 10000; i++) {
                if (ans.compareTo(L) >= 0 && ans.compareTo(R) <= 0) {
                    out.print(ans + " ");
                    valid = true;
                }
                ans.mul(k);
            }
            if (!valid) out.print(-1);
            out.println();
        }

    }

    static class InputReader {
        BufferedReader br;
        StringTokenizer st;

        public InputReader(InputStream inputStream) {
            br = new BufferedReader(new InputStreamReader(inputStream));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }

    static class BigInt extends Number implements Comparable<BigInt> {
        private static final long mask = (1L << 32) - 1;
        private int sign;
        private int len;
        private int[] dig;

        public BigInt(final int sign, final int[] v, final int len) {
            assign(sign, v, len);
        }

        public BigInt(final int sign, final byte[] v, int vlen) {
            while (vlen > 1 && v[vlen - 1] == 0) --vlen;
            dig = new int[(vlen + 3) / 4];
            assign(sign, v, vlen);
        }

        public BigInt(final int sign, final int val) {
            dig = new int[1];
            uassign(sign, val);
        }

        public BigInt(final int sign, final long val) {
            dig = new int[2];
            uassign(sign, val);
        }

        public BigInt(final int val) {
            dig = new int[1];
            assign(val);
        }

        public BigInt(final long val) {
            dig = new int[2];
            assign(val);
        }

        public BigInt(final String s) {
            assign(s);
        }

        public BigInt(final char[] s) {
            assign(s);
        }

        private int parse(final char[] s, int from, final int to) {
            int res = s[from] - '0';
            while (++from < to) res = res * 10 + s[from] - '0';
            return res;
        }

        private void mulAdd(final int mul, final int add) {
            long carry = 0;
            for (int i = 0; i < len; i++) {
                carry = mul * (dig[i] & mask) + carry;
                dig[i] = (int) carry;
                carry >>>= 32;
            }
            if (carry != 0) dig[len++] = (int) carry;
            carry = (dig[0] & mask) + add;
            dig[0] = (int) carry;
            if ((carry >>> 32) != 0) {
                int i = 1;
                for (; i < len && ++dig[i] == 0; ++i) ;
                if (i == len) dig[len++] = 1; //Todo: realloc() for general case?
            }
        }

        private void realloc() {
            final int[] res = new int[dig.length * 2];
            System.arraycopy(dig, 0, res, 0, len);
            dig = res;
        }

        private void realloc(final int newLen) {
            final int[] res = new int[newLen];
            System.arraycopy(dig, 0, res, 0, len);
            dig = res;
        }

        public void assign(final int sign, final int[] v, final int len) {
            this.sign = sign;
            this.len = len;
            dig = v;
        }

        public void assign(final int sign, final byte[] v, final int vlen) {
            len = (vlen + 3) / 4;
            if (len > dig.length) dig = new int[len + 2];
            this.sign = sign;
            int tmp = vlen / 4, j = 0;
            for (int i = 0; i < tmp; i++, j += 4)
                dig[i] = v[j + 3] << 24 | (v[j + 2] & 0xFF) << 16 | (v[j + 1] & 0xFF) << 8 | v[j] & 0xFF;
            if (tmp != len) {
                tmp = v[j++] & 0xFF;
                if (j < vlen) {
                    tmp |= (v[j++] & 0xFF) << 8;
                    if (j < vlen) tmp |= (v[j] & 0xFF) << 16;
                }
                dig[len - 1] = tmp;
            }
        }

        public void assign(final String s) {
            assign(s.toCharArray());
        }

        public void assign(final char[] s) {
            sign = s[0] == '-' ? -1 : 1;

            len = s.length + (sign - 1 >> 1);
            final int alloc = len < 10 ? 1 : (int) (len * 3402L >>> 10) + 32 >>> 5; //3402 = bits per digit * 1024
            if (dig == null || alloc > dig.length) dig = new int[alloc];

            int j = len % 9;
            if (j == 0) j = 9;
            j -= (sign - 1 >> 1);

            dig[0] = parse(s, 0 - (sign - 1 >> 1), j);
            for (len = 1; j < s.length; )
                mulAdd(1_000_000_000, parse(s, j, j += 9));
        }

        public void uassign(final int s, final int val) {
            sign = s;
            len = 1;
            dig[0] = val;
        }

        public void uassign(final int s, final long val) {
            sign = s;
            len = 2;
            if (dig.length < 2) realloc(2);
            dig[0] = (int) (val & mask);
            dig[1] = (int) (val >>> 32);
            if (dig[1] == 0) --len;
        }

        public void assign(final int val) {
            uassign(val < 0 ? -1 : 1, val < 0 ? -val : val);
        }

        public void assign(final long val) {
            uassign(val < 0 ? -1 : 1, val < 0 ? -val : val);
        }

        public boolean isZero() {
            return len == 1 && dig[0] == 0;
        }

        private void setToZero() {
            dig[0] = 0;
            len = 1;
            sign = 1; //Remove?
        }

        public int compareAbsTo(final BigInt a) {
            if (len > a.len) return 1;
            if (len < a.len) return -1;
            for (int i = len - 1; i >= 0; i--)
                if (dig[i] != a.dig[i])
                    if ((dig[i] & mask) > (a.dig[i] & mask)) return 1;
                    else return -1;
            return 0;
        }

        public int compareTo(final BigInt a) {
            if (sign < 0) {
                if (a.sign < 0 || a.isZero()) return -compareAbsTo(a);
                return -1;
            }
            if (a.sign > 0 || a.isZero()) return compareAbsTo(a);
            return 1;
        }

        public boolean equals(final BigInt a) {
            if (len != a.len) return false;
            if (isZero() && a.isZero()) return true;
            if ((sign ^ a.sign) < 0) return false; //In case definition of sign would change...
            for (int i = 0; i < len; i++) if (dig[i] != a.dig[i]) return false;
            return true;
        }


        public boolean equals(final Object o) {
            if (o instanceof BigInt) return equals((BigInt) o);
            return false;
        }


        public int hashCode() {
            int hash = 0; //Todo: Opt and improve.
            for (int i = 0; i < len; i++) hash = (int) (31 * hash + (dig[i] & mask));
            return sign * hash; //relies on 0 --> hash==0.
        }


        public byte byteValue() {
            return (byte) (sign * (dig[0] & 0x7F));
        }


        public short shortValue() {
            return (short) (sign * (dig[0] & 0x7FFF));
        }


        public int intValue() {
            return sign * (dig[0] & 0x7FFFFFFF); //relies on that sign always is either 1/-1.
        }


        public long longValue() {
            return len == 1 ? sign * (dig[0] & mask) : sign * ((dig[1] & 0x7FFFFFFFL) << 32 | (dig[0] & mask));
        }


        public float floatValue() {
            final int s = Integer.numberOfLeadingZeros(dig[len - 1]);
            if (len == 1 && s >= 8) return sign * dig[0];

            int bits = dig[len - 1]; //Mask out the 24 MSBits.
            if (s <= 8) bits >>>= 8 - s;
            else bits = bits << s - 8 | dig[len - 2] >>> 32 - (s - 8); //s-8==additional bits we need.
            bits ^= 1L << 23; //The leading bit is implicit, cancel it out.

            final int exp = (int) (((32 - s + 32L * (len - 1)) - 1 + 127) & 0xFF);
            bits |= exp << 23; //Add exponent.
            bits |= sign & (1 << 31); //Add sign-bit.

            return Float.intBitsToFloat(bits);
        }


        public double doubleValue() {
            if (len == 1) return sign * (dig[0] & mask);

            final int s = Integer.numberOfLeadingZeros(dig[len - 1]);
            if (len == 2 && 32 - s + 32 <= 53) return sign * ((long) dig[1] << 32 | (dig[0] & mask));

            long bits = (long) dig[len - 1] << 32 | (dig[len - 2] & mask); //Mask out the 53 MSBits.
            if (s <= 11) bits >>>= 11 - s;
            else bits = bits << s - 11 | dig[len - 3] >>> 32 - (s - 11); //s-11==additional bits we need.
            bits ^= 1L << 52; //The leading bit is implicit, cancel it out.

            final long exp = ((32 - s + 32L * (len - 1)) - 1 + 1023) & 0x7FF;
            bits |= exp << 52; //Add exponent.
            bits |= (long) sign & (1L << 63); //Add sign-bit.

            return Double.longBitsToDouble(bits);
        }

        public void umul(final int mul) {
            if (mul == 0) {
                setToZero();
                return;
            } //To be removed?

            long carry = 0;
            final long m = mul & mask;
            for (int i = 0; i < len; i++) {
                carry = (dig[i] & mask) * m + carry;
                dig[i] = (int) carry;
                carry >>>= 32;
            }
            if (carry != 0) {
                if (len == dig.length) realloc();
                dig[len++] = (int) carry;
            }
        }

        public void mul(final int mul) {
            if (isZero()) return; //Remove?
            if (mul < 0) {
                sign = -sign;
                umul(-mul);
            } else umul(mul);
        }

        public String toString() {
            if (isZero()) return "0";

            int top = len * 10 + 1;
            final char[] buf = new char[top];
            Arrays.fill(buf, '0');
            final int[] cpy = Arrays.copyOf(dig, len);
            while (true) {
                final int j = top;
                for (long tmp = toStringDiv(); tmp > 0; tmp /= 10)
                    buf[--top] += tmp % 10; //TODO: Optimize.
                if (len == 1 && dig[0] == 0) break;
                else top = j - 13;
            }
            if (sign < 0) buf[--top] = '-';
            System.arraycopy(cpy, 0, dig, 0, len = cpy.length);
            return new String(buf, top, buf.length - top);
        }

        private long toStringDiv() {
            final int pow5 = 1_220_703_125, pow2 = 1 << 13;
            int nextq = 0;
            long rem = 0;
            for (int i = len - 1; i > 0; i--) {
                rem = (rem << 32) + (dig[i] & mask);
                final int q = (int) (rem / pow5);
                rem = rem % pow5;
                dig[i] = nextq | q >>> 13;
                nextq = q << 32 - 13;
            }
            rem = (rem << 32) + (dig[0] & mask);
            final int mod2 = dig[0] & pow2 - 1;
            dig[0] = nextq | (int) (rem / pow5 >>> 13);
            rem = rem % pow5;
            // Applies the Chinese Remainder Theorem.
            // -67*5^13 + 9983778*2^13 = 1
            final long pow10 = (long) pow5 * pow2;
            rem = (rem - pow5 * (mod2 - rem) % pow10 * 67) % pow10;
            if (rem < 0) rem += pow10;
            if (dig[len - 1] == 0 && len > 1)
                if (dig[--len - 1] == 0 && len > 1)
                    --len;
            return rem;
        }

    }

    static class OutputWriter extends PrintWriter {
        public OutputWriter(OutputStream outputStream) {
            super(new BufferedOutputStream(outputStream));
        }

        public OutputWriter(Writer writer) {
            super(writer);
        }

        public void close() {
            super.close();
        }

    }
}