//Daria Magiera - 1
import java.util.Arrays;

class NSum {


    static class Stack {

        public int[] stackArr;
        private int maxSize;
        public int topOfStack;

//        public Stack(int max) {
//            maxSize = max;
//            stackArr = new int[maxSize];
//            topOfStack = 0;
//        }

        public boolean isEmpty() {
            return (topOfStack == 0);
        }

        public int top() {
            return stackArr[topOfStack - 1];
        }

        public void push(int c) {
            stackArr[topOfStack] = c;
            topOfStack++;
        }

        public int pop() {
            int c = stackArr[topOfStack - 1];
            topOfStack--;
            return c;
        }

        public int size() {
            return topOfStack;
        }

        public Stack() {
            maxSize = 20;
            stackArr = new int[maxSize];
            topOfStack = 0;
        }
    }

    public static int[] popEverything(int i, Stack stack, int[] subArr, int top) {

        if (i < top) {
            subArr[i] = stack.pop();
            return popEverything(++i, stack, subArr, top);
        }
        else {
            return subArr;
        }
    }

    public static int[] findNComponentsRecAux(int last, int a, int n, Stack stack) {

        if (last < 0) {
            int[] arr = new int[0];
            return arr;
        }

        stack.push(a);
        int z = last - (int)Math.pow(a, n);
        if (z == 0) {
            int subArr[] = new int[stack.topOfStack];
            int top = stack.topOfStack;
            return popEverything(0, stack, subArr, top);
        }
        int c = (int)Math.pow( z, 1. / n);

        if (c >= a && c != 1) {
            c = a - 1;
        }

        if (z != 1 && c == 1) {
            int sciagam = stack.pop();
            if (stack.isEmpty()) {
                int[] arr = new int[0];
                return arr;
            }

            return findNComponentsRecAux((int)Math.pow(sciagam, n) + z, sciagam - 1, n, stack);

        }
        if (z > c * (int)Math.pow(c, n)) {

            stack.pop();
            if (stack.isEmpty()) {
                int[] arr = new int[0];
                return arr;
            }
            int sciagam = stack.pop();
            return findNComponentsRecAux((int)Math.pow(sciagam, n) + last, sciagam - 1, n, stack);
        }

//--------------
        return findNComponentsRecAux(z, c, n, stack);

    }

    public static int[] findNComponentsRec(int x, int n) {

        Stack stack = new Stack();
        int a = (int)Math.pow(x, 1. / n);
        return findNComponentsRecAux(x, a, n, stack);

    }

    public static int[] findNComponentsIter(int x, int n) {

        Stack stack = new Stack();
        int a = (int)Math.pow( x, 1. / n);
        stack.push(a);
        int z = x - (int)Math.pow(a, n);

        if (z == 0) {

            int subArr[] = new int[stack.topOfStack];
            int top = stack.topOfStack;
            for (int i = 0; i < top; i++) {
                subArr[i] = stack.pop();
            }
            return subArr;

        } // jesli to po prostu potega jednej liczby ^^^

        stack.pop();

        while (z != 0) {

            stack.push(a);
            z = x - (int) Math.pow(a, n);

            int c = (int)Math.pow( z, 1. / n);

            if (c >= a && c != 1) {
                c = a - 1;
            }

            if (z != 1 && c == 1) {
                int sciagam = stack.pop();
                if (stack.isEmpty()) {
                    int[] arr = new int[0];
                    return arr;
                }

                x = (int) Math.pow(sciagam, n) + z;
                a = sciagam - 1;

                continue;
            }

            if (z > c * (int) Math.pow(c, n)) {

                stack.pop();
                if (stack.isEmpty()) {
                    int[] arr = new int[0];
                    return arr;
                }
                int sciagam = stack.pop();
                x = (int) Math.pow(sciagam, n) + x;
                a = sciagam - 1;

                continue;
            }

            x = z;
            a = c;

            continue;

        } //-----------------------------------koniec while

        int subArr[] = new int[stack.topOfStack];
        int top = stack.topOfStack;
        for (int i = 0; i < top; i++) {
            subArr[i] = stack.pop();
        }
        return subArr;


    } //koniec funkcji

}

public class Source {

    public static void main(String[] args) {
        //152512 nie dziala
        System.out.println(Arrays.toString(NSum.findNComponentsRec(10020001, 3)));

    }
}