Клітинний автомат
Автомат клітинний — це набір клітин на сітці певної форми, що розвивається через дискретні часові кроки відповідно до правил, які визначають новий стан клітини на основі станів сусідніх клітин. Порядок клітинного автомата — це кількість клітин, які він містить. Клітини автомата порядку 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-кроків.