eolymp
bolt
Try our new interface for solving problems
Problems

Сейф

Сейф

Time limit 0.05 seconds
Memory limit 64 MiB

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

z1.jpg

####Завдання

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

Input data

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

Output data

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

####Оцінювання

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

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

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

Examples

Input example #1
7 5
11 12 11 9 9 9 9
Output example #1
1 2 3 2 3 2 1
Source XXX Всеукраїнська олімпіада з інформатики, Рівне 2-5 квітня 2017