ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1949. Лучший фильм галактики

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Профессор Валентин Владимирович, член галактической киноакадемии, завтра примет участие в голосовании по номинации «лучший фильм». Но профессор ещё не смотрел ни одного из n фильмов-номинантов, да и сегодня у него совсем нет времени. Он решил попросить о помощи k своих студентов, которые до сих пор не получили у него зачёт. Если студенты посмотрят все фильмы, а потом кратко расскажут о своих впечатлениях, то этой информации будет вполне достаточно, чтобы сделать выбор…
Каждый из фильмов-номинантов показывают в кинотеатре только один раз — i-й фильм начинается в момент времени ai и заканчивается в момент времени bi. Студент может посмотреть за день сколько угодно фильмов, но любой из них он должен посмотреть полностью от начала и до конца. Студент не может смотреть два фильма одновременно. Известно также, что в i-м фильме снимается ci красивых актрис. Студент откажется идти на фильм, если в нём будет меньше красивых актрис, чем в предыдущем просмотренном им фильме.
Валентин Владимирович дал студентам подробные указания на тот случай, если они не успеют посмотреть за день все фильмы. Фильмы занумерованы в порядке убывания известности их режиссёров, фильмы известных режиссёров интересуют профессора больше. Если студенты могут посмотреть за день набор фильмов A либо набор фильмов B, то набор A предпочительнее, если существует такое i, что:
  • фильмы с номерами от 1 до i − 1 либо содержатся и в A, и в B, либо не содержатся ни в A, ни в B;
  • фильм с номером i содержится в A и не содержится в B.
Помогите Валентину Владимировичу и его студентам найти самый предпочтительный набор фильмов.

Исходные данные

В первой строке записаны целые числа n и k (1 ≤ n ≤ 100; 1 ≤ kn). В i-й из n следующих строк записаны целые числа ai, bi, ci (0 ≤ ai < bi ≤ 86 399; 1 ≤ ci ≤ 10 000).

Результат

Выведите строку из n цифр, задающую самый предпочительный набор фильмов. На i-й позиции должна стоять единица, если i-й фильм входит в набор, и ноль в противном случае.

Примеры

исходные данныерезультат
4 2
1 5 10
3 6 20
5 10 9
5 10 10
1101
4 1
1 5 10
3 6 20
5 10 9
5 10 10
1001
Автор задачи: Виталий Белокобыльский, Сергей Маджуга
Источник задачи: Открытое личное первенство УрФУ по программированию 2012