问题描述

有一根围绕原点 $O$ 顺时针旋转的棒 $OA$, 初始时指向正上方 ($Y$轴正向)。 在平面中有若干物件, 第 $i$ 个物件的坐标为 $\left(x_{i}, y_{i}\right)$, 价值为 $z_{i}$。当棒扫到某个 物件时, 棒的长度会瞬间增长 $z_{i}$, 且物件瞬间消失（棒的顶端恰好碰到物件也 视为扫到), 如果此时增长完的棒又额外碰到了其他物件, 也按上述方式消去 (它和上述那个点视为同时消失)。

如果将物件按照消失的时间排序, 则每个物件有一个排名, 同时消失的物 件排名相同, 请输出每个物件的排名, 如果物件永远不会消失则输出 -1。

输入格式

输入第一行包含两个整数 $n、 L$, 用一个空格分隔, 分别表示物件数量和棒 的初始长度。

接下来 $n$ 行每行包含第三个整数 $x_{i}, y_{i}, z_{i}$。

输出格式

输出一行包含 $n$ 整数, 相邻两个整数间用一个空格分隔, 依次表示每个物件的排名。

5 2
0 1 1
0 3 2
4 3 5
6 8 1
-51 -33 2

1 1 3 4 -1

评测用例规模与约定

对于 30% 的评测用例, $1 \leq n \leq 500$;

对于 60% 的评测用例, $1 \leq n \leq 5000$;

对于所有评测用例, $1 \leq n \leq 200000,-10^9 \leq x_i, y_i \leq 10^9, 1 \leq L, z_i \leq 10^9$。