$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