时间限制：1秒　　内存限制：256M

---

【题目描述】

　　一个细胞自动机包含 \(n\) 个格子，每个格子的取值为 \(0 \sim m-1\)。给定距离 \(d\)，则每次操作后每个格子的值将变为到它距离不超过 \(d\) 的所有格子在操作之前的值之和除以 \(m\) 的余数，其中 \(i\) 和 \(j\) 的距离为 \(min \{|i-j|,n-|i-j| \}\)。给定 \(n,m,d,k\) 和自动机各格子的初始值，你的任务是计算 \(k\) 次操作以后各格子的值。

　　如下图，\(n=5,m=3,d=1\)，一次操作将把图a变成图b。比如，与格子 3 距离不超过1的格子（即格子 2,3,4）在操作之前的值分别是2,2,1，因此从 操作后格子3的值为(2+2+1)mod 3=2。

【输入格式】

　　第一行包含四个整数 \(n,m,d,k\)。第二行包含 \(n\) 个 \(0..m-1\)的整数，即各格子的初始值。

【输出格式】

　　输出一行，包含 \(n\) 个 \(0..m-1\) 的整数，即 \(k\) 次操作后各格子的值。

【输入输出样例1】

　Input

5 3 1 1
1 2 2 1 2

　Output

2 2 2 2 1

【输入输出样例2】

　Input

5 3 1 10
1 2 2 1 2

　Output

2 0 0 2 2

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤500\)，\(1≤m≤10^6\)

【来源】

　　Mr.he**