Назовем массив \(a\) отсортированным, если \(a_1 \leq a_2 \leq \ldots \leq a_{n - 1} \leq a_{n}\).
Вам даны два любимых целых числа фермера Джона, \(n\) и \(k\). Он просит вас найти любой массив \(a_1, a_2, \ldots, a_{n}\), удовлетворяющий следующим требованиям:
- \(1 \leq a_i \leq 10^9\) для всех \(1 \leq i \leq n\);
- Среди всех \(n\) циклических сдвигов \(a\), ровно \(k\) из них отсортированы.\(^\dagger\)
Если такого массива \(a\) не существует, выведите \(-1\).
\(^\dagger\) \(x\)-й (\(1 \leq x \leq n\)) циклический сдвиг массива \(a\) является массивом \(a_x, a_{x+1} \ldots a_n, a_1, a_2 \ldots a_{x - 1}\). Если \(c_{x, i}\) обозначает \(i\)-й элемент \(x\)-го циклического сдвига \(a\), то ровно \(k\) таких значений \(x\) должны удовлетворять \(c_{x,1} \leq c_{x,2} \leq \ldots \leq c_{x, n - 1} \leq c_{x, n}\).
Например, циклические сдвиги для \(a = [1, 2, 3, 3]\) следующие:
- \(x = 1\): \([1, 2, 3, 3]\) (отсортировано);
- \(x = 2\): \([2, 3, 3, 1]\) (не отсортировано);
- \(x = 3\): \([3, 3, 1, 2]\) (не отсортировано);
- \(x = 4\): \([3, 1, 2, 3]\) (не отсортировано).
Выходные данные
Для каждого набора входных данных выведите одну строку:
- если существует подходящий массив \(a\), выведите \(n\) целых чисел, равняющихся \(a_1, a_2, \ldots, a_{n}\);
- в противном случае, выведите \(-1\).
Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных \(a = [1, 1]\) удовлетворяет условиям \(n = 2, k = 2\):
Два циклических сдвига \(a\): \([a_1, a_2]\) и \([a_2, a_1]\), оба равняются \([1, 1]\) и отсортированы.
Во втором наборе входных данных \(a = [69\,420, 69, 420]\) удовлетворяет \(n = 3, k = 1\):
Три циклических сдвига \(a\): \([a_1, a_2, a_3]\), \([a_2, a_3, a_1]\), \([a_3, a_1, a_2]\) равняются \([69\,420, 69, 420]\), \([69, 420, 69\,420]\) и \([420, 69\,420, 69]\) соответственно.
Отсортирован только \([69, 420, 69\,420]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 2
3 1
3 2
|
1 1
69420 69 420
-1
|