0400. Физкультура

Имя входного файла: array.in
Имя выходного файла: array.out
Ограничение по времени: 2 s
Ограничение по памяти: 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.inarray.out
5 3 3 1 2 3 1 2
5 2 1 -1

Решение, выводящие только -1 будет оценен в 0 баллов.


Источник: Муниципальный этап всероссийской олимпиады школьников по информатике, 12 декабря 2014 года.

Обсудить       Отправить решение



Версия для печати