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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.TreeSet;


public final class BubbleX_Finals_F{

	static boolean verb=true;
	static void log(Object X){if (verb) System.err.println(X);}
	static void log(Object[] X){if (verb) {for (Object U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X,int L){if (verb) {for (int i=0;i<L;i++) System.err.print(X[i]+" ");System.err.println("");}}
	static void log(long[] X){if (verb) {for (long U:X) System.err.print(U+" ");System.err.println("");}}

	static void logWln(Object X){if (verb) System.err.print(X);}
	static void info(Object o){	System.out.println(o);}
	static void output(Object o){outputWln(""+o+"\n");	}
	static void outputWln(Object o){try {out.write(""+ o);} catch (Exception e) {}}

	static long powerMod(long b,long e,long m){
		long x=1;
		while (e>0) {
			if (e%2==1)
				x=(b*x)%m;
			b=(b*b)%m;
			e=e/2;
		}
		return x; 
	}

	static int MX=Integer.MAX_VALUE;


	// Global vars
	static BufferedWriter out;
	static InputReader reader;

	static long mod=1000000007;


	
	static void process() throws Exception {



		out = new BufferedWriter(new OutputStreamWriter(System.out));
		reader=new InputReader(System.in);
		int n=reader.readInt();
		int M=reader.readInt();
		long a=reader.readInt();
		long Q=reader.readInt();
		
		
		/*
		long[] ar=new long[n];
		Arrays.fill(ar,a);
		log("official");
		
		for (int u=0;u<M;u++){
			for (int i=0;i+1<n;i++){
				ar[i]=ar[i]*ar[i+1];
				if (ar[i]>=mod)
					ar[i]%=mod;
			}
			log(ar);
		}
		log("-----");
		*/
		
		long mod=1;
		long aa=a;
		while (aa!=1){
			mod++;
			aa*=a;
			if (aa>=Q)
				aa%=Q;
		}
		log("mod:"+mod);
		//mod=Q;
		long[] fact=new long[M+1];
		fact[0]=1;
		for (int i=1;i<=M;i++){
			fact[i]=fact[i-1]*i;
			if (fact[i]>=mod)
				fact[i]%=mod;
		}
		long[] diff=new long[n+1];
		for (int k=0;k<=Math.min(n-1,M);k++){
				long cmk=fact[M];
				long base=fact[k]*fact[M-k];
				if (base>=mod)
					base%=mod;
				cmk*=powerMod(base,mod-2,mod);
				if (cmk>=mod)
					cmk%=mod;
				//logWln(cmk+" ");
				diff[0]+=cmk;
				if (diff[0]>=mod)
					diff[0]-=mod;
				diff[n-k]+=mod-cmk;
				if (diff[n-k]>=mod)
					diff[n-k]-=mod;
				// k contribue 
		}
	
		long b=0;
		for (int i=0;i<n;i++){
			b+=diff[i];
			if (b>=mod)
				b-=mod;
			outputWln(powerMod(a,b,Q)+" ");
		}
		output("");
		
		try {
			out.close();
		}
		catch (Exception e){}


	}


	public static void main(String[] args) throws Exception {
		process();

	}

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

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

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}


		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res=new StringBuilder();
			do {
				res.append((char)c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			//log("d:"+d);
			if (d=='-') {
				neg=true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			//log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			//log("d:"+d);
			if (d=='-') {
				neg=true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			//log("res:"+res);
			if (neg)
				return -res;
			return res;

		}




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


}
/*

10 2 2 1000000007

*/