CF164C.Machine Programming

One remarkable day company "X" received k machines. And they were not simple machines, they were mechanical programmers! This was the last unsuccessful step before switching to android programmers, but that's another story.

The company has now n tasks, for each of them we know the start time of its execution s__i, the duration of its execution t__i, and the company profit from its completion c__i. Any machine can perform any task, exactly one at a time. If a machine has started to perform the task, it is busy at all moments of time from s__i to s__i + t__i - 1, inclusive, and it cannot switch to another task.

You are required to select a set of tasks which can be done with these k machines, and which will bring the maximum total profit.

某一天，公司“X”收到了 $k$ 台机器。这些可不是普通机器，而是机械程序员！这是公司在转向安卓程序员之前最后一步（也是失败的一步），但那是另一个故事了。

目前公司共有 $n$ 项任务，对每项任务 $i$，我们已知其开始执行时间 $s_i$、执行时长 $t_i$，以及完成该任务可为公司带来的收益 $c_i$。任意一台机器均可执行任意一项任务，但同一时刻至多只能执行一项任务。一旦某台机器开始执行某项任务，它将在时间区间 $[s_i,\, s_i + t_i - 1]$（含端点）内的所有时刻均处于忙碌状态，且无法中途切换至其他任务。

你需要从这 $n$ 项任务中选出一个子集，使得该子集中的所有任务能够被这 $k$ 台机器所执行，并使得总收益最大。

The first line contains two integer numbers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 50) — the numbers of tasks and machines, correspondingly.

The next n lines contain space-separated groups of three integers s__i, t__i, c__i (1 ≤ s__i, t__i ≤ 109, 1 ≤ c__i ≤ 106), s__i is the time where they start executing the i-th task, t__i is the duration of the i-th task and c__i is the profit of its execution.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 1000$，$1 \leq k \leq 50$），分别表示任务数和机器数。

接下来的 $n$ 行每行包含三个由空格分隔的整数 $s_i,\,t_i,\,c_i$（$1 \leq s_i,\,t_i \leq 10^9$，$1 \leq c_i \leq 10^6$），其中 $s_i$ 表示第 $i$ 个任务的开始执行时间，$t_i$ 表示第 $i$ 个任务的执行时长，$c_i$ 表示执行该任务所获得的收益。

Print n integers _x_1, _x_2, ..., x__n. Number x__i should equal 1, if task i should be completed and otherwise it should equal 0.

If there are several optimal solutions, print any of them.

输出 n 个整数 _x_₁, _x_₂, ..., x__n。若任务 i 应当完成，则 x__i 的值应为 1；否则应为 0。

若存在多个最优解，输出其中任意一个即可。

In the first sample the tasks need to be executed at moments of time 2 ... 8, 1 ... 3 and 4 ... 4, correspondingly. The first task overlaps with the second and the third ones, so we can execute either task one (profit 5) or tasks two and three (profit 6).

在第一个样例中，各任务的执行时间分别为 $2\ldots8$、$1\ldots3$ 和 $4\ldots4$。第一个任务与第二个和第三个任务均存在重叠，因此我们可选择执行任务一（收益为 $5$），或执行任务二和任务三（收益为 $6$）。