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>.
//Created by Aminul on 4/2/2019.

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class CF852F {
    static long f[], inv[], mod = (int) 1e9 + 7;

    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = in.nextInt();
        int m = in.nextInt();
        int a = in.nextInt();
        int q = in.nextInt();
        mod = phi(a, q);
        initialize(m);

        long exp[] = new long[n];
        for (int i = 0, j = n - 1; j >= 0; i++, j--) {
            if (i <= m) exp[j] = nCr(m, i);
            if (j + 1 < n) exp[j] += exp[j + 1];
            exp[i] %= mod;
        }

        for (long e : exp) {
            pw.print(bigMod(a, e, q) + " ");
        }
        pw.println();

        pw.close();
    }

    static void initialize(int n) {
        f = new long[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            f[i] = (f[i - 1] * i) % mod;
        }
        inv = new long[n + 1];
        inv[n] = modInverse(f[n], mod);
        for (int i = n - 1; i >= 0; i--) {
            inv[i] = (inv[i + 1] * (i + 1)) % mod;
        }
    }

    static long nCr(int n, int c) {
        long u = f[n], d = (inv[c] * inv[n - c]) % mod;
        return (u * d) % mod;
    }

    public static long modInverse(long a, long m) {
        a = mod(a, m);
        return a == 0 ? 0 : mod((1 - modInverse(m % a, a) * m) / a, m);
    }

    public static long mod(long a, long m) {
        long A = (a % m);
        return A >= 0 ? A : A + m;
    }

    static long bigMod(long a, long p, long m) { // returns (a^p) % m
        long res = 1 % m, x = a % m;
        while (p > 0) {
            if ((p & 1) > 0) res = (res * x) % m;
            x = (x * x) % m;
            p >>= 1;
        }
        return res;
    }

    static long phi(long a, long q) { // multiplicative order, finds smallest P, such tha (a^p % q) = 1
        long res = 1;
        long c = a;
        while (c % q != 1) {
            c = (c * a + q) % q;
            res++;
        }
        return res;
    }


    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }
}