Circular Cellular Automaton

A cellular automaton is a collection of cells arranged on a grid of a fixed shape that evolves through a number of discrete time steps according to rules that determine the new state of each cell from the states of its neighbours. The order of a cellular automaton is the number of cells it contains; the cells of an automaton of order $n$ are numbered from $1$ to $n$.

The order of a cell is the number of distinct values it can hold. The values of a cell of order $m$ are the integers from $0$ to $m-1$.

One of the most fundamental properties of a cellular automaton is the grid on which it lives. Here we study a special kind: the circular cellular automaton of order $n$ whose cells have order $m$. We call it an $n,m$-automaton.

The distance between cells $i$ and $j$ of an $n,m$-automaton is $\min(|i-j|,; n-|i-j|)$. The $d$-environment of a cell is the set of all cells whose distance from it is at most $d$.

On each $d$-step, the values of all cells are replaced simultaneously. The new value of cell $i$ is the sum of the values of the cells in the $d$-environment of $i$, taken modulo $m$.

Compute the state of the $n,m$-automaton after $k$ consecutive $d$-steps.

The first line contains four integers $n$, $m$, $d$, and $k$ ($1 \le n \le 500$, $1 \le m \le 1{,}000{,}000$, $0 \le d < n/2$, $1 \le k \le 10{,}000{,}000$). The second line contains $n$ integers between $0$ and $m-1$ — the initial values of the automaton's cells.

Output the values of the $n,m$-automaton's cells after $k$ $d$-steps, separated by single spaces on one line.