Istnieje jednowymiarowy automat komórkowy składający się z $N$ komórek. Komórki są ponumerowane od $0$ do $N-1$.

Każda komórka ma stan reprezentowany przez nieujemną liczbę całkowitą mniejszą niż $M$. Stany komórek zmieniają się w dyskretnych krokach czasowych. Stan $i$-tej komórki w chwili $t$ oznaczamy przez $S(i,t)$. Stan w chwili $t+1$ definiuje równanie

$$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}$$

gdzie $A$, $B$ i $C$ są nieujemnymi stałymi całkowitymi. Dla $i<0$ lub $N\le i$ definiujemy $S(i,t)=0$.

Mając definicję automatu i początkowe stany komórek, napisz program obliczający stany komórek w zadanej chwili $T$.

Wejście

Wejście jest ciągiem zestawów danych. Każdy zestaw ma następujący format.

$$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)$$

Pierwszy wiersz zestawu danych składa się z sześciu liczb całkowitych: $N$, $M$, $A$, $B$, $C$ i $T$. $N$ to liczba komórek. $M$ jest modułem w równaniu (1). $A$, $B$ i $C$ są współczynnikami równania (1). Wreszcie $T$ to chwila, dla której należy obliczyć stany.

Możesz założyć, że $0<N\le50$, $0<M\le1000$, $0\le A,B,C<M$ oraz $0\le T\le10^9$.

Drugi wiersz składa się z $N$ liczb całkowitych, z których każda jest nieujemna i mniejsza niż $M$. Reprezentują one stany komórek w chwili $0$.

Wiersz zawierający sześć zer oznacza koniec wejścia.

Wyjście

Dla każdego zestawu danych wypisz wiersz zawierający stany komórek w chwili $T$. Format wyjścia jest następujący.

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

Każdy stan musi być reprezentowany jako liczba całkowita, a liczby muszą być rozdzielone pojedynczą spacją.

Przykład

Wejście 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

Wyjście 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