A. Сильнейшая команда
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Представим, что вы проектируете гача-игру по «Магической битве» и хотите составить сильнейшую команду из $$$k$$$ персонажей. Как это обычно бывает в гача-играх, сюжетные разногласия и детали здесь не имеют значения, но по дизайну игры все-таки есть определенные правила, которым команда должна соответствовать.

Всего у игрока есть $$$n$$$ персонажей, каждый характеризуется тремя параметрами:

  • $$$a_i$$$ — проклятая энергия (если $$$a_i \lt 0$$$, то герой — проклятье, если $$$a_i \gt 0$$$, то маг, а если ровно $$$0$$$, то просто человек);
  • $$$b_i$$$ — хаотичность (если $$$b_i \lt 0$$$, то герой хаотичный, если $$$b_i \gt 0$$$, то порядочный, а если ровно $$$0$$$, то нейтральный);
  • $$$c_i$$$ — уровень силы.

Например, Тодо Аой обладает положительной проклятой энергией, но является хаотичным персонажем, тогда как Чосо — нейтральное проклятье.

По правилам игры на игровую команду персонажей накладываются следующие ограничения:

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

Определите команду из $$$k$$$ героев, подходящую под эти условия и имеющую максимальную суммарную силу героев. Гарантируется, что подходящий набор героев существует.

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

В первой строке ввода даны два целых числа $$$n$$$ и $$$k$$$ — общее число доступных героев и необходимое число героев в команде ($$$1 \le k \le n \le 2 \cdot 10^5$$$).

В $$$i$$$-й из следующих $$$n$$$ строк через пробел перечислены целые числа $$$a_i$$$, $$$b_i$$$ и $$$c_i$$$ — параметры $$$i$$$-го героя ($$$-10^9 \le a_i, b_i \le 10^9$$$; $$$1 \le c_i \le 10^9$$$).

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

Выведите $$$k$$$ различных чисел от $$$1$$$ до $$$n$$$ в произвольном порядке — номера героев, составляющих оптимальную команду. Если существует несколько оптимальных ответов, выведите любой из них.

Гарантируется, что ответ всегда существует.

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

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

ПодзадачаБаллыДоп. ограничения Необходимые подзадачи Информация о проверке
0–примеры из условияполная
15$$$n \le 2000$$$0полная
210$$$k = 1$$$0первая ошибка
310$$$k = 2$$$0, 2первая ошибка
415$$$b_i \ge 0$$$ для всех $$$i$$$0первая ошибка
515не более одного $$$b_ilt; 0$$$0, 4первая ошибка
615либо все $$$a_i \ge 0$$$, либо все $$$a_i \le 0$$$0первая ошибка
715если $$$b_ilt; 0$$$, то $$$a_i = 0$$$0первая ошибка
815нет0 – 7первая ошибка
Примеры
Входные данные
4 2
-1 1 5
0 1 4
2 1 6
0 -1 3
Выходные данные
3 2
Входные данные
7 4
1 1 8
0 1 7
2 -1 10
-1 1 9
0 -1 6
-2 1 5
0 1 4
Выходные данные
1 2 7 3