Банк країни Олімпія запросив Петрика перевірити новітню систему безпеки. Його завдання якомога скоріше відчинити сейф, розгадавши такий шифр. Навколо центрального кола сейфа записано p натуральних чисел. Для того, щоб відкрити сейф, необхідно замінити всі числа на інші натуральні таким чином, що кожне число в сумі з q-1 наступними числами давало б початкове число. Наприклад, якщо навколо кола сейфа вказано числа 11, 12, 11, 9, 9, 9, 9 та q=5, то потрібно встановити числа: 1, 2, 3, 2, 3, 2, 1 і сейф буде відкрито!

Завдання

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

Вхідні дані

У першому рядку вхідних даних знаходяться два натуральних числа p і q відповідно, (1 ≤ q ≤ p ≤ 104). p і q – прості числа. У наступному рядку задано p натуральних чисел, що не перевищують 105 – вихідна конфігурація сейфу.

Вихідні дані

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

Оцінювання

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

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

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