有一个由 $N$ 个细胞组成的一维细胞自动机。细胞从 $0$ 到 $N - 1$ 编号。

每个细胞都有一个状态，用一个小于 $M$ 的非负整数表示。细胞的状态随着离散的时间步长而演变。我们用 $S(i, t)$ 表示第 $i$ 个细胞在时间 $t$ 的状态。在时间 $t + 1$ 的状态由以下方程定义：

$$S(i, t + 1) = (A \times S(i - 1, t) + B \times S(i, t) + C \times S(i + 1, t)) \bmod M \quad (1)$$

其中 $A$、$B$ 和 $C$ 是非负整数常量。对于 $i < 0$ 或 $N \le i$，我们定义 $S(i, t) = 0$。

给定自动机的定义和细胞的初始状态，你的任务是编写一个程序，计算在指定时间 $T$ 时各细胞的状态。

输入格式

输入由一系列数据集组成。每个数据集的格式如下：

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

每个数据集的第一行包含六个整数，即 $N$、$M$、$A$、$B$、$C$ 和 $T$。$N$ 是细胞的数量。$M$ 是方程 (1) 中的模数。$A$、$B$ 和 $C$ 是方程 (1) 中的系数。最后，$T$ 是你需要计算状态的时间。

你可以假设 $0 < N \le 50$，$0 < M \le 1000$，$0 \le A, B, C < M$ 且 $0 \le T \le 10^9$。

第二行包含 $N$ 个整数，每个整数都是非负的且小于 $M$。它们表示时间为零（初始时刻）时各细胞的状态。

包含六个零的一行表示输入结束。

输出格式

对于每个数据集，输出一行，包含时间 $T$ 时各细胞的状态。输出格式如下：

S(0, T) S(1, T) ... 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