ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1949. The Best Picture in the Galaxy

Time limit: 1.0 second
Memory limit: 64 MB
Professor Valentin Vladimirovich, member of the Galaxy Academy, tomorrow takes part in voting for nomination “The Best Picture”. But professor haven’t watched any of n nominee movies yet and he doesn’t in fact have time today. He decided to ask help from his k students, who still haven’t got credit for his subjects. If the students watch all the movies and then tell professor briefly about their impressions, this information will be enough to make a choice.
Each of the nominee movies is shown in the movie halls only once, the i'th movie starts at time ai and finishes at time bi. A student can watch any number of movies through the day, but he must watch each one from start to finish. A student can’t watch two movies simultaneously. It is also known that ci beautiful actresses star in the i'th movie. A student won’t go for a movie if less actresses star in it than in the previous movie he watched.
Valentin Vladimirovich gave students detailed instructions in case they can’t watch all the movies in one day. The movies are numbered in descending order according to descending popularity of their directors. If students can see either set A of movies or set B of movies, the set A is more preferable if there is such i that:
  • the movies with numbers from 1 to i − 1 are either present in both sets A and B, or not present in neither A nor B;
  • the i'th movie is present in the set A and is not present in the set B.
Find the most preferable set of movies for Valentin Vladimirovich and his students.


The first line contains integers n and k (1 ≤ n ≤ 100; 1 ≤ kn). The ith of the next n lines contains integers ai, bi, ci (0 ≤ ai < bi ≤ 86 399; 1 ≤ ci ≤ 10 000).


Output a string of n digits, specifying the most preferable set of movies. One should be at the position i if the i'th movie is present in this set, and zero should be there in the opposite case.


4 2
1 5 10
3 6 20
5 10 9
5 10 10
4 1
1 5 10
3 6 20
5 10 9
5 10 10
Problem Author: Vitaliy Belokobilskiy, Sergey Madzhuga
Problem Source: Open Ural FU Personal Contest 2012