非凡的一天,公司“X”收到了 k 台机器。而且它们不是简单的机器,它们是机械程序员!这是转向 android 程序员之前最后一个不成功的步骤,但那是另一个故事了。
公司现在有 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。如果任务 i 应完成,则数字 xi 应等于 1,否则应等于 0。
如果有多个最优解,则打印其中任意一个。
示例
输入 #1
3 1 2 7 5 1 3 3 4 1 3
输出 #1
0 1 1
输入 #2
5 2 1 5 4 1 4 5 1 3 2 4 1 2 5 6 1
输出 #2
1 1 0 0 1
注意
在第一个示例中,任务需要相应地在时间 2 ... 8、1 ... 3 和 4 ... 4 时刻执行。第一个任务与第二个和第三个任务重叠,因此我们可以执行任务一(利润 5)或任务二和任务三(利润 6)。