C. Автоматное программирование
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В один замечательный день в компанию «X» завезли k автоматов. И не простых автоматов, а автоматов-программистов! Это был последний неудачный шаг перед переходом на андроидов-программистов, но это уже совсем другая история.

В компании сейчас n задач, для каждой из которых известно время начала ее выполнения si, длительность ее выполнения ti и прибыль компании от ее завершения ci. Любой автомат может выполнять любую задачу, ровно одну в один момент времени. Если автомат начал выполнять задачу, то он занят все моменты времени с si по si + ti - 1 включительно и не может переключиться на другую задачу.

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

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

В первой строке записаны два целых числа n и k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 50) — количества задач и автоматов, соответственно.

В следующих n строках через пробелы записаны тройки целых чисел si, ti, ci (1 ≤ si, ti ≤ 109, 1 ≤ ci ≤ 106), si — время начала выполнения i-го задания, ti — длительность i-го задания, а ci — прибыль от его выполнения.

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

Выведите n целых чисел x1, x2, ..., xn. Число xi должно быть равно 1, если задачу i следует выполнить, и 0 в противном случае.

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

Примеры
Входные данные
3 1
2 7 5
1 3 3
4 1 3
Выходные данные
0 1 1
Входные данные
5 2
1 5 4
1 4 5
1 3 2
4 1 2
5 6 1
Выходные данные
1 1 0 0 1
Примечание

В первом примере задания требуют выполнения в моменты времени 2 ... 8, 1 ... 3 и 4 ... 4, соответственно. Первое задание пересекается со вторым и третьим, поэтому можно выполнять либо его одно (прибыль 5), либо второе и третье (прибыль 6).