русский
english
0400. Физкультура
| Input file name: | array.in |
| Output file name: | array.out |
| Time limit: | 2 s |
| Memory limit: | 256 megabytes |
В классе Богдана учится N человек. На уроке физкультуры учитель Валерий Витальевич решил построить всех учеников в линию. Поскольку в классе все оказались весьма высокими, Валерий Витальевич сказал каждому ученику выбрать себе число от 1 до K и построиться, используя это число вместо роста. Причем, ученикам не возбраняется выбирать одинаковые числа.
По школе недавно прошел слух, что у учителя баг: если в получившемся строе длина наибольшей неубывающей подпоследовательности окажется равной L, то он разрешает подергать себя за усы.
Пусть строй это набор чисел a, тогда подпоследовательность длины t в строе – это набор элементов ai1, ai2, …, ait, причем i1 < i2 < …< it. Подпоследовательность – неубывающая, если выполняется ai1 ≤ ai2 ≤ … ≤ ait. Неубывающая подпоследовательность – наибольшая, если у нее максимальная длина среди всевозможных неубывающих подпоследовательностей. Например, в наборе чисел 1;2;3;1;2 существует 3 наибольших неубывающих подпоследовательности: 1;2;3, 1;2;2, 1;1;2.
Класс поручил Богдану выбрать каждому ученику число и расставить всех так, чтобы можно было подергать Валерия Витальевича за усы. Помогите Богдану справиться с задачей, иначе его опять будут дразнить. Если задача не имеет решения, то выведите единственное число -1.
Формат входного файла
В единственной строке входного файла содержатся три целых числа 1 ≤ N ≤ 105, 1 ≤ K ≤ 105, 1 ≤ L ≤ N.
Формат выходного файла
В единственной строке выходного файла выведите ровно N чисел – строй, который должен сформировать Богдан. Если вариантов несколько, выведите любой. Если ответа не существует,то выведите -1.
Пример:
| array.in | array.out |
|---|---|
| 5 3 3 | 1 2 3 1 2 |
| 5 2 1 | -1 |
Решение, выводящие только -1 будет оценен в 0 баллов.