Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Trong phòng thí nghiệm, các kỹ sư đang xây dựng một chiếc bảng tính tự động, gồm có N chiếc máy tính con và hiển thị ra N màn hình, đánh dấu từ 0 tới N - 1.

Ban đầu, tại mỗi màn hình sẽ là giá trị đầu vào ( < M) của máy tính con. S(i,t) là trạng thái hiển thị của màn hình thứ i tại thời điểm t. Trạng thái tại mỗi màn hình thay đổi theo thời gian và được xác định theo công thức:

S(i; t + 1) = (A x S(i - 1; t) + B x S(i; t) + C x S(i + 1; t)) mod M.

Với i ≤ 0 hoặc N ≤ i thì S(i,t) = 0.

Nhiệm vụ của bạn là xác định trạng thái của N màn hình tại thời điểm T.

Input

Gồm nhiều bộ test. Mỗi bộ test gồm:

Dòng 1 có 6 số N M A B C T (0 < N ≤ 50, 0 < M ≤ 1000, 0 ≤ A,B,C < M, 0 ≤ T ≤ 10⁹).

Dòng 2 gồm N số, là trạng thái của các màn hình tại thời điểm ban đầu:
S(0; 0) S(1; 0) ... S(N - 1; 0)

Input kết thúc bởi 6 số 0.

Output

Với mỗi test, hãy in ra trạng thái của N ô tại thời điểm T theo mẫu:

S(0; T)  S(1; T)  .... S(N - 1; T)

Example

Input:

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

Output:

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