Сейф
Банк страны Олимпия пригласил Петрика для проверки новейшей системы безопасности. Его задача — как можно быстрее открыть сейф, разгадав шифр. Вокруг центрального круга сейфа записаны 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 ≤ 10^4). p и q — простые числа. В следующей строке задано p натуральных чисел, не превышающих 10^5 — исходная конфигурация сейфа.
Выходные данные
В единственной строке выведите p натуральных чисел, не превышающих 10^9, которые откроют сейф. Гарантируется, что по крайней мере одна такая конфигурация существует. Если возможных ответов несколько, выведите любой из них.
Примеры
Оценивание
Дополнительно гарантируются такие условия:
30 % тестов: p ≤ 7, существует ответ, в котором все искомые числа ≤ 7
60 % тестов: p ≤ 500, существует ответ, в котором все искомые числа ≤ 500