A \textit{cellular automaton} is a collection of cells on a grid of specified shape that evolves through a number of discrete time steps according to a set of rules that describe the new state of a cell based on the states of neighboring cells. The \textit{order of the cellular automaton} is the number of cells it contains. Cells of the automaton of order n are numbered from \textbf{1} to \textbf{n}. The \textit{order of the cell} is the number of different values it may contain. Usually, values of a cell of order m are considered to be integer numbers from \textbf{0} to \textbf{m-1}. One of the most fundamental properties of a cellular automaton is the type of grid on which it is computed. In this problem we examine the special kind of cellular automaton --- circular cellular automaton of order n with cells of order\textbf{m}. We will denote such kind of cellular automaton as \textbf{n,m}-\textit{automaton}. A distance between cells \textbf{i} and \textbf{j} in \textbf{n,m}-automaton is defined as \textbf{min(|i-j|, n-|i-j|)}. A \textbf{d}-\textit{environment of a cell} is the set of cells at a distance not greater than \textbf{d}. On each \textbf{d}-\textit{step} values of all cells are simultaneously replaced by new values. The new value of cell \textbf{i} after \textbf{d}-\textit{step} is computed as a sum of values of cells belonging to the \textbf{d}-enviroment of the cell \textbf{i} modulo \textbf{m}. The following picture shows \textbf{1}-step of the \textbf{5,3}-automaton. \includegraphics{https://static.e-olymp.com/content/8e/8e4e79ea025c6b41fbe34e20454f38ec304962d3.jpg} The problem is to calculate the state of the \textbf{n,m}-automaton after \textbf{k} \textbf{d}-steps. \InputFile The first line of the input contains four integer numbers \textbf{n}, \textbf{m}, \textbf{d}, and \textbf{k} (\textbf{1} ≤ \textbf{n} ≤ \textbf{500}, \textbf{1} ≤ \textbf{m} ≤ \textbf{1000000}, \textbf{0} ≤ \textbf{d} < \textbf{n/2},\textbf{1} ≤ \textbf{k} ≤ \textbf{10000000}). The second line contains \textbf{n} integer numbers from \textbf{0} to \textbf{m-1} --- initial values of the automaton's cells. \OutputFile Output the values of the \textbf{n,m}-automaton's cells after \textbf{k} \textbf{d}-steps.