21671번 - Москва – Ханты-Мансийск 스페셜 저지다국어

В связи с проведением в Ханты-Мансийске Всероссийской олимпиады школьников по информатике агентство авиаперевозок обязано перевезти самолётами всех участников олимпиады. Всего за m дней, пронумерованных от 1 до m, из Москвы в Ханты-Мансийск хотят вылететь n пассажиров, в том числе и участники олимпиады.

Все желающие вылететь в Ханты-Мансийск заполнили анкеты, в которых указали информацию о возможных днях вылета и об участии в олимпиаде. Информация о возможных днях вылета i-го пассажира указана в виде пары чисел (a_i, b_i). Это означает, что пассажир согласен вылететь в любой день, начиная с a_i и по b_i включительно, и не может вылететь в другие дни.

Самолёт из Москвы в Ханты-Мансийск вылетает всего один раз в день и вмещает не более k пассажиров. Необходимо распределить пассажиров по дням вылета таким образом, чтобы улетело как можно большее количество пассажиров, при этом, все участники Всероссийской олимпиады должны улететь обязательно.

Напишите программу, определяющую распределение пассажиров по дням вылета, при котором максимизируется количество перевезённых пассажиров, или определяющую, что такого распределения не существует.

В первой строке входного файла записаны три натуральных числа — n, m и k (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000, 1 ≤ k ≤ 100 000). Далее следуют n строк, i-я из которых содержит результаты заполнения анкеты пассажиром с порядковым номером i в виде трёх целых чисел, первые два из которых — самый ранний и самый поздний дни вылета a_i и b_i (1 ≤ a_i ≤ b_i ≤ m), а последнее число равно 0, если пассажир не является участником Всероссийской олимпиады, и равно 1, если является. Гарантируется, что хотя бы один пассажир является участником Всероссийской олимпиады. Числа в каждой строке разделены пробелами.

В первой строке выходного файла выведите максимальное количество пассажиров l, которых можно перевезти из Москвы в Ханты-Мансийск. Если невозможно выполнить поставленную задачу, то в первой строке необходимо вывести число 0. В случае положительного ответа выведите во второй строке n чисел, а именно, для каждого пассажира выведите номер дня, в который запланирован его вылет, либо 0, если этому пассажиру не нашлось места в оптимальном распределении. Числа во второй строке разделяйте пробелами. Если оптимальных распределений несколько, выведите любое из них.