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.*;
import java.util.*;

public class F852 {

	public static void main(String[] args) throws IOException {
		IO io = new IO(System.in);

		int n = io.nextInt();
		int m = io.nextInt();
		int a = io.nextInt();
		int q = io.nextInt();
		long phi = phi(a, q);

		a = a % q;
//		io.println(phi);

		long[] pow = new long[n];
		pow[0] = 1;
		for (int i = 1; i < n && i <= m; i++) {
			pow[i] = pow[i-1] * (m-i+1) % phi;
			pow[i] = pow[i] * modInvPrime(i,phi) % phi;
//			cur = (((cur * ((t - b + 1))) * modInvPrime(b,phi)) + phi) % phi;
			// io.println(cur);
//			sum = (sum + cur + phi) % phi;
//			pow.add(sum);
		}
		
		for (int i = 1; i < n; i++) {
			pow[i] += pow[i-1];
			pow[i] %= phi;
		}

		for (int i = n-1; i >= 0; i--) {
			io.print(modpow(a,pow[i],q) + " ");
		}

		io.close();
	}
	
	static long modInvPrime(long a, long p) {
		return modpow(a,p-2,p);
	}

	static long modpow(long a, long b, long mod) {
		long res = 1 % mod;
		while (b > 0) {
			if ((b & 1) == 1) {
				res = res * a % mod;
			}
			a = a * a % mod;
			b >>>= 1;
		}
		return res;
	}

	static long phi(long a, long q) {
		long res = 1;
		long c = a;
		while (c % q != 1) {
			c = (c * a + q) % q;
			res++;
		}
		return res;
	}

	static class IO extends PrintWriter {
		static BufferedReader r;
		static StringTokenizer t;

		public IO(InputStream i) {
			super(new BufferedOutputStream(System.out));
			r = new BufferedReader(new InputStreamReader(i));
			t = new StringTokenizer("");
		}

		public String next() throws IOException {
			while (!t.hasMoreTokens()) {
				t = new StringTokenizer(r.readLine());
			}
			return t.nextToken();
		}

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

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

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
	}
}