Problem: There is a one-dimensional cellular automaton consisting of N cells. Cells are numbered from 0 to N − 1.

Each cell has a state represented as a non-negative integer less than M. The states of cells evolve through discrete time steps. We denote the state of the i-th cell at time t as S(i, t). The state at time t + 1 is defined by the equation

S(i, t + 1) = (A × S(i − 1, t) + B × S(i, t) + C × S(i + 1, t)) mod M,         (1)

where A, B and C are non-negative integer constants. For i < 0 or N ≤ i, we define S(i, t) = 0.

Given an automaton definition and initial states of cells, your mission is to write a program that computes the states of the cells at a specified time T.



Input

The input is a sequence of datasets. Each dataset is formatted as follows.

N M A B C T
S(0, 0) S(1, 0) ... S(N − 1, 0)


The first line of a dataset consists of six integers, namely N, M, A, B, C and T. N is the number of cells. M is the modulus in the equation (1). A, B and C are coefficients in the equation (1). Finally, T is the time for which you should compute the states.

You may assume that 0 < N ≤ 50, 0 < M ≤ 1000, 0 ≤ A, B, C < M and 0 ≤ T ≤ 109.

The second line consists of N integers, each of which is non-negative and less than M. They represent the states of the cells at time zero.

A line containing six zeros indicates the end of the input.

Output

For each dataset, output a line that contains the states of the cells at time T. The format of the output is as follows.

S(0, T) S(1, T) ... S(N − 1, T)

Each state must be represented as an integer and the integers must be separated by a space.

Example

Input

5 4 1 3 2 0
0 1 2 0 1
5 7 1 3 2 1
0 1 2 0 1
5 13 1 3 2 11
0 1 2 0 1
5 5 2 0 1 100
0 1 2 0 1
6 6 0 2 3 1000
0 1 2 0 1 4
20 1000 0 2 3 1000000000
0 1 2 0 1 0 1 2 0 1 0 1 2 0 1 0 1 2 0 1
30 2 1 0 1 1000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
30 2 1 1 1 1000000000
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
30 5 2 3 1 1000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0


Output

0 1 2 0 1
2 0 0 4 3
2 12 10 9 11
3 0 4 2 1
0 4 2 0 4 4
0 376 752 0 376 0 376 752 0 376 0 376 752 0 376 0 376 752 0 376
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 3 2 2 2 3 3 1 4 3 1 2 3 0 4 3 3 0 4 2 2 2 2 1 1 2 1 3 0

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.lang.ArrayIndexOutOfBoundsException;
import java.math.*;


class Main {
	static Scanner sc = new Scanner(new InputStreamReader(System.in));
	public static void main(String[] args) throws Exception {
		while(true) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			int t = sc.nextInt();
			if(n+m+a+b+c+t == 0) break;

			int[] s = new int[n];
			for (int i = 0; i < n; i++) {
				s[i] = sc.nextInt();
			}
			// System.out.println(Arrays.toString(s));

			int[][] matrix = new int[n][n];

			for (int i = 0; i < n; i++) {
				matrix[i][i] = b;
			}
			for (int i = 1; i < n; i++) {
				matrix[i][i-1] = a;
				matrix[i-1][i] = c;
			}
			//		System.out.println("--- before matrix ----------");
			//		for (int i = 0; i < n; i++) {
			//			StringBuffer buf = new StringBuffer();
			//			for (int j = 0; j < n; j++) {
			//				buf.append(matrix[i][j] + " ");
			//			}
			//			System.out.println(buf.toString().trim());
			//		}

			matrix = modPow(matrix, t, m);

			//		System.out.println("--- after matrix ----------");
			//		for (int i = 0; i < n; i++) {
			//			StringBuffer buf = new StringBuffer();
			//			for (int j = 0; j < n; j++) {
			//				buf.append(matrix[i][j] + " ");
			//			}
			//			System.out.println(buf.toString().trim());
			//		}


			//		System.out.println("--- ans --------------------");
			StringBuffer buf = new StringBuffer();
			for (int i = 0; i < n; i++) {
				int ans = 0;
				for (int j = 0; j < n; j++) {
					ans += matrix[i][j] * s[j];
				}
				buf.append((ans % m) + " ");
			}
			System.out.println(buf.toString().trim());
		}
	}

	static int[][] modPow(int[][] matrix, int t, int m) {
		// System.out.println("modpow " + t + " " + m);
		matrixMod(matrix, m);
		if(t == 0) {
			int n = matrix.length;
			int[][] ans = new int[n][n];
			for (int i = 0; i < n; i++) {
				ans[i][i] = 1;
			}
			return ans;
		}
		if(t == 1) return matrix;

		if(t % 2 == 0) {
			int[][] mult = matrixMod(matrixMult(matrix, matrix), m);
			return matrixMod(modPow(mult, t/2, m), m);
		} else {
			int[][] mult = matrixMod(matrixMult(matrix, matrix), m);
			return matrixMod(matrixMult(modPow(mult, t/2, m), matrix), m);
		}
	}

	static int[][] matrixMod(int[][] a, int m) {
		int n = a.length;
		int[][] b = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				b[i][j] = a[i][j] % m;
			}
		}
		return b;
	}

	static int[][] matrixMult(int[][] a, int[][] b){
		int n = a.length;
		int[][] c = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					c[i][j] += a[i][k] * b[k][j];
				}
			}
		}
		return c;
	}
}


/**
 * 複素数
 */
class Complex {
	static Complex I = new Complex(0, 1);

	double r = 0.0;
	double i = 0.0;
	Complex(double r, double i) {
		this.r = r;
		this.i = i;
	}

	/**
	 * 和
	 */
	public Complex add(Complex a) {
		return new Complex(r * a.r, i + a.i);
	}

	/**
	 * 積
	 */
	public Complex mul(Complex a) {
		return new Complex(
				r * a.r - i * a.i,
				r * a.i + i * a.r);
	}

	public Complex divide(double a) {
		return new Complex(r/a, i/a);
	}

	public Complex inverse() {
		double b = 1 / (r*r + i*i);
		return new Complex(r/b, -i/b);
	}


	@Override
	public String toString(){
		return r + "+" + i + "i";
	}
}




// --- ここから下はライブラリ ----------
/**
 * MyUtil
 * @author yoshikyoto
 */
class MyIO {
	public static int toInt(boolean[] a){
		int pow = 1, ret = 0, l = a.length;
		for(int i = 0; i < l; i++){
			if(a[i]) ret += pow;
			pow *= 2;
		}
		return ret;
	}
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static int ins[];
	public static int[] readIntMap() throws IOException{return parseInt(readLine().split(" "));}
	public static int readIntMap(int i) throws Exception{
		if(i == 0) ins = readIntMap();
		return ins[i];
	}
	public static int[][] readIntMap(int n, int m) throws IOException{
		int[][] ret = new int[n][];
		for(int i = 0; i < n; i++) ret[i] = readIntMap();
		return ret;
	}
	public static int[] readIntToMap(int n) throws IOException{
		int[] ret = new int[n];
		for(int i = 0; i < n; i++) ret[i] = readInt();
		return ret;
	}
	public static int[] readNoDistIntMap() throws IOException{
		String[] strs = readLine().split("");
		int l = strs.length;
		int[] ret = new int[l-1];
		for(int i = 1; i < l; i++)
			ret[i-1] = parseInt(strs[i]);
		return ret;
	}
	public static String readLine() throws IOException{return br.readLine();}
	public static int readInt() throws IOException{return Integer.parseInt(br.readLine());}
	public static int[] parseInt(String[] arr){
		int[] res = new int[arr.length];
		for(int i = 0; i < arr.length; i++)res[i] = Integer.parseInt(arr[i]);
		return res;
	}
	public static double[] parseDouble(String[] arr){
		double[] res = new double[arr.length];
		for(int i = 0; i < arr.length; i++)res[i] = Double.parseDouble(arr[i]);
		return res;
	}
	public static boolean[] parseBool(String[] arr){
		int[] t = parseInt(arr);
		boolean[] res = new boolean[t.length];
		for(int i = 0; i < t.length; i++){
			if(t[i] == 1){res[i] = true;
			}else{res[i] = false;}
		}
		return res;
	}
	public static int parseInt(Object o){
		return Integer.parseInt(o.toString());
	}
}