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

В классе Богдана учится N человек. На уроке физкультуры учитель Валерий Витальевич решил построить всех учеников в линию. Поскольку в классе все оказались весьма высокими, Валерий Витальевич сказал каждому ученику выбрать себе число от 1 до K и построиться, используя это число вместо роста. Причем, ученикам не возбраняется выбирать одинаковые числа.

По школе недавно прошел слух, что у учителя баг: если в получившемся строе длина наибольшей неубывающей подпоследовательности окажется равной L, то он разрешает подергать себя за усы.

Пусть строй это набор чисел a, тогда подпоследовательность длины t в строе – это набор элементов a_i1, a_i2, …, a_it, причем i₁ < i₂ < …< i_t. Подпоследовательность – неубывающая, если выполняется a_i1 ≤ a_i2 ≤ … ≤ a_it. Неубывающая подпоследовательность – наибольшая, если у нее максимальная длина среди всевозможных неубывающих подпоследовательностей. Например, в наборе чисел 1;2;3;1;2 существует 3 наибольших неубывающих подпоследовательности: 1;2;3, 1;2;2, 1;1;2.

Класс поручил Богдану выбрать каждому ученику число и расставить всех так, чтобы можно было подергать Валерия Витальевича за усы. Помогите Богдану справиться с задачей, иначе его опять будут дразнить. Если задача не имеет решения, то выведите единственное число -1.

Формат входного файла

В единственной строке входного файла содержатся три целых числа 1 ≤ N ≤ 10⁵, 1 ≤ K ≤ 10⁵, 1 ≤ L ≤ N.

Формат выходного файла

В единственной строке выходного файла выведите ровно N чисел – строй, который должен сформировать Богдан. Если вариантов несколько, выведите любой. Если ответа не существует,то выведите -1.

Пример:

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

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

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



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