Consider an array A with N elements, all being the same integer a.

Define the product transformation as a simultaneous update Ai = Ai·Ai + 1, that is multiplying each element to the element right to it for <image>, with the last number AN remaining the same. For example, if we start with an array A with a = 2 and N = 4, then after one product transformation A = [4, 4, 4, 2], and after two product transformations A = [16, 16, 8, 2].

Your simple task is to calculate the array A after M product transformations. Since the numbers can get quite big you should output them modulo Q.

Input

The first and only line of input contains four integers N, M, a, Q (7 ≤ Q ≤ 109 + 123, 2 ≤ a ≤ 106 + 123, <image>, <image> is prime), where <image> is the multiplicative order of the integer a modulo Q, see notes for definition.

Output

You should output the array A from left to right.

Example

Input

2 2 2 7


Output

1 2 

Note

The multiplicative order of a number a modulo Q <image>, is the smallest natural number x such that ax mod Q = 1. For example, <image>.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
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);
        PrintWriter out = new PrintWriter(outputStream);
        TaskF solver = new TaskF();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskF {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            int a = in.nextInt();
            int q = in.nextInt();
            int p = 1;
            for (; p < 2000200; ++p)
                if (Mod.powMod(a, p, q) == 1) {
                    break;
                }

            int[] f = new int[n];
            int _2powm = 1;
            //m;
            _2powm = Mod.powMod(2, m, p);
            int lastc = 1;

            for (int i = 0; i < n; ++i) {
                if (i >= m) {
                    f[i] = _2powm;
                    continue;
                }

                if (i == 0) {
                    f[i] = 1;
                    continue;
                }
                lastc = Mod.mulMod(lastc, m - i + 1, p);
                lastc = Mod.mulMod(lastc, MathUtils.modInverse(i, p), p);
                f[i] = Mod.addMod(f[i - 1], lastc, p);
            }

            for (int i = 0; i < n; ++i) {
                f[i] = Mod.powMod(a, f[i], q);
            }

            MathUtils.reverseArray(f);
            for (int i = 0; i < n; ++i) {
                out.print(f[i] + " ");
            }
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

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

        public static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }

    static class MathUtils {
        static long _invMod(long a, long b) {
            return 1 < a ? b - _invMod(b % a, a) * b / a : 1;
        }

        public static int modInverse(int a, int m) {
//		long B = fecmaPow(a, m - 2, m);
//		if (B < 0) {
//			B += (Math.abs(B) / m + 1) * m;
//			B %= m;
//		}
//		return (int) B;

            return (int) _invMod(a, m);

        }

        public static void swap(int[] a, int i, int j) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }

        public static void reverseArray(int[] a) {
            int size = a.length;
            for (int i = 0, mid = size >> 1, j = size - 1; i < mid; i++, j--) {
                swap(a, i, j);
            }
        }

    }

    static class Mod {
        public static final boolean DEBUG = false;

        public static int addMod(int a, int b, long MOD) {
            if (DEBUG) return a + b;

            while (a < 0)
                a += MOD;
            while (b < 0)
                b += MOD;
            return (int) (((long) a + (long) b) % MOD);
        }

        public static int mulMod(int a, int b, long MOD) {
            if (DEBUG) return a * b;

            while (a < 0)
                a += MOD;
            while (b < 0)
                b += MOD;
            return (int) (((long) a) * ((long) b) % MOD);
        }

        public static int powMod(int a, int n, long MOD) {
            if (n < 0) throw new RuntimeException();
            if (n == 0) return 1;

            int temp = powMod(a, n / 2, MOD);
            temp = mulMod(temp, temp, MOD);
            if (n % 2 == 1) {
                temp = mulMod(temp, a, MOD);
            }

            return temp;
        }

    }
}

