Клеточный автомат
Автомат, называемый клеточным, представляет собой набор клеток, расположенных на сетке определенной формы, который изменяется с течением времени по дискретным шагам в соответствии с набором правил. Эти правила определяют новое состояние каждой клетки на основе состояний её соседей. Порядок клеточного автомата — это общее количество клеток в нём. Клетки автомата порядка n пронумерованы от 1 до n.
Порядок клетки — это количество различных значений, которые она может принимать. Обычно значения клетки порядка m представлены целыми числами от 0 до m-1.
Одним из ключевых свойств клеточного автомата является тип сетки, на которой он работает. В этой задаче мы рассматриваем круговой клеточный автомат порядка n с клетками порядка m. Такой автомат обозначается как n,m-автомат.
Расстояние между клетками i и j в n,m-автомате определяется как min(|i-j|, n-|i-j|). d-окружение клетки — это набор клеток, находящихся на расстоянии не более d от неё.
На каждом d-шаге значения всех клеток одновременно заменяются новыми. Новое значение клетки i после d-шага вычисляется как сумма значений клеток, входящих в d-окружение клетки i, взятая по модулю m.
На следующем изображении показан 1-шаг 5,3-автомата.
Ваша задача — вычислить состояние n,m-автомата после выполнения k d-шагов.
Входные данные
Первая строка ввода содержит четыре целых числа n, m, d и k (1 ≤ n ≤ 500, 1 ≤ m ≤ 1000000, 0 ≤ d < n/2, 1 ≤ k ≤ 10000000). Вторая строка содержит n целых чисел от 0 до m-1, представляющих начальные значения клеток автомата.
Выходные данные
Выведите значения клеток n,m-автомата после выполнения k d-шагов.