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.*;
import java.math.BigInteger;
import java.util.InputMismatchException;
import java.util.Scanner;

public class Main {
    private static InputReader ir;
    private static OutputWriter ow;
    final static int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        initS();
        //initF("INPUT.TXT", "OUTPUT.TXT");
        task();
        exit();
    }

    private static void task() throws Exception {
        Scanner scanner = new Scanner(System.in);
        BigInteger l = scanner.nextBigInteger(), r = scanner.nextBigInteger();
        int k = scanner.nextInt();
        BigInteger res = new BigInteger("1");
        boolean p = false;
        while (res.compareTo(r) <= 0) {
            if (res.compareTo(l) >= 0) {
                ow.print(res + " ");
                p = true;
            }
            res = res.multiply(new BigInteger((Long.valueOf(k).toString())));
        }
        if (!p) ow.print(-1);
    }

    private static void initS() throws IOException {
        ir = new InputReader(System.in);
        ow = new OutputWriter(System.out);
    }

    private static void initF(String inName, String outName) throws IOException {
        ir = new InputReader(new FileInputStream(inName));
        ow = new OutputWriter(new FileOutputStream(outName));
    }

    private static void exit() throws Exception {
        ir.close();
        ow.close();
    }
}


class InputReader implements AutoCloseable {
    private final InputStream in;
    private int capacity;
    private byte[] buffer;
    private int len = 0;
    private int cur = 0;

    public InputReader(InputStream stream) {
        this(stream, 100_000);
    }

    public InputReader(InputStream stream, int capacity) {
        this.in = stream;
        this.capacity = capacity;
        buffer = new byte[capacity];
    }

    private int read() {
        if (cur >= len) {
            try {
                cur = 0;
                len = in.read(buffer, 0, capacity);
                if (len <= 0)
                    return -1;
            } catch (IOException e) {
                throw new InputMismatchException();
            }
        }
        return buffer[cur++];
    }

    private boolean isSpace(int c) {
        return c == ' ' || isEscape(c);
    }

    private boolean isEscape(int c) {
        return c == '\n' || c == '\t' || c == '\r' || c == -1;
    }

    private int readSkipSpace() {
        int c;
        do {
            c = read();
        } while (isSpace(c));
        return c;
    }

    int nextInt() {
        int c = readSkipSpace();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res = res * 10 + c - '0';
            c = read();
        } while (!isSpace(c));
        res *= sgn;
        return res;
    }

    public long nextLong() {
        int c = readSkipSpace();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res = res * 10 + c - '0';
            c = read();
        } while (!isSpace(c));
        res *= sgn;
        return res;
    }

    int nextChar() {
        return readSkipSpace();
    }

    String nextLine() {
        StringBuilder res = new StringBuilder();
        int c = readSkipSpace();
        do {
            res.append((char) (c));
            c = read();
        } while (!isEscape(c));
        return res.toString();
    }

    @Override
    public void close() throws Exception {
        in.close();
    }
}


class OutputWriter implements Flushable, AutoCloseable {
    private byte[] buf;
    private int capacity;
    private int count;
    private OutputStream out;

    public OutputWriter(OutputStream stream) {
        out = stream;
        capacity = 10_000;
        buf = new byte[capacity];
    }

    public OutputWriter(OutputStream stream, int capacity) {
        if (capacity <= 0)
            throw new IllegalArgumentException("capacity <= 0");
        out = stream;
        this.capacity = capacity;
        buf = new byte[capacity];
    }

    public void write(int b) throws IOException {
        if (count >= buf.length)
            flushBuffer();
        buf[count++] = (byte)b;
    }

    public void write(byte[] bytes, int off, int len) throws IOException {
        if (len >= buf.length) {
            flushBuffer();
            out.write(bytes, off, len);
            return;
        }
        if (len > buf.length - count)
            flushBuffer();
        System.arraycopy(bytes, off, buf, count, len);
        count += len;
    }

    public void write(byte[] bytes) throws IOException {
        write(bytes, 0, bytes.length);
    }

    public void print(int i) throws IOException {
        print(String.valueOf(i));
    }

    public void print(long l) throws IOException {
        print(String.valueOf(l));
    }

    public void print(String str) throws IOException {
        write(str.getBytes());
    }

    public void println() throws IOException {
        print("\n");
    }

    public void println(String str) throws IOException {
        print(str);
        print("\n");
    }

    public void println(int i) throws IOException {
        print(i);
        println();
    }

    public void println(long l) throws IOException {
        print(l);
        println();
    }

    public void print(String separator, Object... objects) throws IOException {
        if (objects == null) return;
        for (int i = 0; i < objects.length; ++i) {
            if (i != 0 && separator != null) print(separator);
            print(objects[i].toString());
        }
    }

    private void flushBuffer() throws IOException {
        if (count > 0) {
            out.write(buf, 0, count);
            count = 0;
        }
    }

    @Override
    public void flush() throws IOException {
        flushBuffer();
        out.flush();
    }

    @Override
    public void close() throws Exception {
        flush();
        out.close();
    }
}