$N$ 個のセルからなる一次元セルオートマトンがあります。セルには $0$ から $N-1$ までの番号が付いています。

各セルは $M$ 未満の非負整数で表される状態を持ちます。セルの状態は離散的な時間ステップに沿って変化します。時刻 $t$ における $i$ 番目のセルの状態を $S(i,t)$ と表します。時刻 $t+1$ の状態は次の式で定義されます。

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

ここで $A$、$B$、$C$ は非負整数の定数です。$i<0$ または $N\le i$ のとき、$S(i,t)=0$ と定義します。

オートマトンの定義とセルの初期状態が与えられたとき、指定された時刻 $T$ におけるセルの状態を計算するプログラムを書いてください。

入力

入力は複数のデータセットからなります。各データセットは次の形式です。

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

データセットの最初の行は六つの整数 $N$、$M$、$A$、$B$、$C$、$T$ からなります。$N$ はセルの数です。$M$ は式 (1) の法です。$A$、$B$、$C$ は式 (1) の係数です。最後の $T$ は状態を計算する時刻です。

$0<N\le50$、$0<M\le1000$、$0\le A,B,C<M$、$0\le T\le10^9$ と仮定して構いません。

二行目は $N$ 個の整数からなり、それぞれ非負で $M$ 未満です。これらは時刻 $0$ におけるセルの状態を表します。

六つの 0 を含む行は入力の終わりを表します。

出力

各データセットについて、時刻 $T$ におけるセルの状態を一行に出力してください。出力の形式は次のとおりです。

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

各状態は整数で表し、整数は一つの空白で区切ってください。

入出力例

入力 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

出力 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