Hay un autómata celular unidimensional formado por $N$ celdas. Las celdas están numeradas del $0$ al $N-1$.

Cada celda tiene un estado representado por un entero no negativo menor que $M$. Los estados de las celdas evolucionan en pasos de tiempo discretos. Denotamos el estado de la celda $i$ en el instante $t$ por $S(i,t)$. El estado en el instante $t+1$ se define mediante la ecuación

$$S(i,t+1)=\bigl(A\times S(i-1,t)+B\times S(i,t)+C\times S(i+1,t)\bigr)\bmod M.\tag{1}$$

donde $A$, $B$ y $C$ son constantes enteras no negativas. Para $i<0$ o $N\le i$, definimos $S(i,t)=0$.

Dadas la definición de un autómata y los estados iniciales de las celdas, tu misión es escribir un programa que calcule los estados de las celdas en un instante especificado $T$.

Entrada

La entrada es una secuencia de conjuntos de datos. Cada conjunto tiene el siguiente formato.

$$N\quad M\quad A\quad B\quad C\quad T$$

$$S(0,0)\quad S(1,0)\quad\ldots\quad S(N-1,0)$$

La primera línea de un conjunto contiene seis enteros: $N$, $M$, $A$, $B$, $C$ y $T$. $N$ es el número de celdas. $M$ es el módulo de la ecuación (1). $A$, $B$ y $C$ son los coeficientes de la ecuación (1). Por último, $T$ es el instante para el que debes calcular los estados.

Puedes suponer que $0<N\le50$, $0<M\le1000$, $0\le A,B,C<M$ y $0\le T\le10^9$.

La segunda línea contiene $N$ enteros, cada uno no negativo y menor que $M$. Representan los estados de las celdas en el instante $0$.

Una línea que contiene seis ceros indica el final de la entrada.

Salida

Para cada conjunto de datos, imprime una línea con los estados de las celdas en el instante $T$. El formato de salida es el siguiente.

$$S(0,T)\quad S(1,T)\quad\ldots\quad S(N-1,T)$$

Cada estado debe representarse como un entero y los enteros deben estar separados por un espacio.

Ejemplos

Entrada 1

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

Salida 1

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