Сейф

Національний банк Олімпії запросив Петрика перевірити новітню систему безпеки. Його завдання — якнайшвидше відкрити сейф, розшифрувавши його код. Навколо центрального кола сейфа записано $p$ натуральних чисел. Щоб відкрити сейф, потрібно замінити кожне число іншим натуральним так, щоб для кожної позиції сума цього числа і наступних q-1 чисел (по колу) дорівнювала початковому числу у цій позиції.

Наприклад, якщо навколо кола сейфа вказано числа 11, 12, 11, 9, 9, 9, 9 та q=5, потрібно встановити числа 1, 2, 3, 2, 3, 2, 1 — і сейф буде відкрито!

Завдання

Напишіть програму, яка за початковою конфігурацією сейфа і числом $q$ відновлює одну з можливих конфігурацій, що відкриють сейф.

\InputFileУ першому рядку вхідних даних знаходяться два натуральні числа $p$ та $q$ (1 \leq q \leq p \leq 10^4). Обидва числа $p$ і $q$ — прості. У наступному рядку задано $p$ натуральних чисел, що не перевищують 10^5 — початкова конфігурація сейфа.

\OutputFileУ єдиному рядку виведіть $p$ натуральних чисел, що не перевищують 10^9, які відкриють сейф. Гарантується, що принаймні одна така конфігурація існує. Якщо можливих відповідей декілька, виведіть будь-яку з них.

\ScoringДодатково гарантуються такі умови:

1. Для 30% тестів: p \leq 7, існує відповідь, у якій усі шукані числа $\le 7$.

2. Для 60% тестів: p \leq 500, існує відповідь, у якій усі шукані числа $\le 500$.