B. Крупная закупка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После окончания разборок с украденным бриллиантом, новообразованной команде «Хищных птиц» нужно заняться множеством организационных вопросов. Разумеется, одним из самых важных является покупка оружия, без которого у них вряд ли есть шансы на долгое существование.

В магазине есть $$$n$$$ различных видов оружия, $$$i$$$-й из которых обладает мощностью $$$a_i$$$. Дина Лэнс, отвечающая за оружейные запасы, делает выбор по следующим критериям:

  1. Требуется купить ровно $$$m$$$ единиц оружия.
  2. Среди $$$m$$$ купленных единиц оружия должно быть не менее $$$k$$$ различных видов.
  3. Среди всех наборов, удовлетворяющих первым двум критериям, надо выбрать набор с максимальной суммарной мощностью.
  4. Среди всех таких наборов максимальной мощности требуется выбрать такой, в котором максимальное количество единиц оружия одного вида минимально.

Помогите ей с выбором и найдите такой оптимальный набор. Если наборов с такими свойствами несколько, выведите любой подходящий.

Входные данные

В первой строке даны три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ — количество видов оружия в магазине, необходимое число единиц оружия и минимальное число различных видов в наборе ($$$1 \le k \le n \le 500\,000$$$, $$$k \le m \le 500\,000$$$).

В следующей строке даны $$$n$$$ целых чисел $$$a_i$$$ — мощность оружия $$$i$$$-го вида ($$$0 \le a_i \le 10^9$$$).

Выходные данные

Выведите $$$m$$$ целых чисел $$$b_i$$$ — номера видов оружия, которые входят в искомый набор ($$$1 \le b_i \le n$$$). Для каждого вида, его номер должен встречаться столько раз, сколько он входит в набор.

Система оценки

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

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
110Все $$$a_i$$$ различныпервая ошибка
210$$$m = k$$$первая ошибка
320$$$k = 1$$$первая ошибка
420$$$n, m \le 1\,000$$$первая ошибка
540Без дополнительных ограничений1, 2, 3, 4первая ошибка
Примеры
Входные данные
5 3 2
1 2 3 4 5
Выходные данные
5 4 5
Входные данные
5 3 3
1 2 3 4 5
Выходные данные
5 4 3