Алексей — серьёзный математик, и он любит решать серьёзные задачи. Вот, например, одна из этих задач.
Необходимо построить массив из целых чисел длины n, в котором не менее k различных чисел, такой, что количество различных сумм на подотрезках минимально. Другими словами, необходимо рассмотреть все подотрезки массива, посчитать на каждом сумму чисел и убрать повторяющиеся суммы. Количество оставшихся сумм и нужно минимизировать.
Исходные данные
В единственной строке даны целые числа n, k (1 ≤ k ≤ n ≤ 500) через пробел.
Результат
В единственной строке выведите n целых чисел, разделённых пробелом — ответ на задачу. Все числа должны быть не больше 106 по модулю. Гарантируется, что существует оптимальное решение, в котором все числа не более 105 по модулю. Если есть несколько оптимальных ответов, выведите любой из них.
Примеры
исходные данные | результат |
---|
1 1
| -987654
|
3 2
| 0 7 0
|
Замечания
Рассмотрим второй тестовый пример и обозначим сумму чисел на отрезке с l по r как sum(l, r) (индексация начинается с 1). Тогда sum(1, 1) = sum(3, 3) = 0, sum(1, 2) = sum(1, 3) = sum(2, 2) = sum(2, 3) = 7, то есть количество различных сумм равно 2.
Автор задачи: Никита Сивухин (подготовка — Алексей Данилюк, Никита Сивухин)
Источник задачи: Уральская региональная командная олимпиада по программированию 2015