Problem Description

There is a stick $OA$ rotating clockwise around the origin $O$. At the beginning, it points straight upward (the positive direction of the $Y$ axis). There are several objects on the plane. The coordinates of the $i$-th object are $\left(x_{i}, y_{i}\right)$, and its value is $z_{i}$. When the stick sweeps over an object, the length of the stick instantly increases by $z_{i}$, and the object disappears instantly (if the tip of the stick just touches the object, it is also considered swept). If, after this increase, the stick additionally touches other objects, they are also removed in the same way (they are considered to disappear at the same time as the object above).

If we sort the objects by their disappearance time, then each object has a rank, and objects that disappear at the same time have the same rank. Please output the rank of each object. If an object will never disappear, output $-1$.

Input Format

The first line contains two integers $n$ and $L$, separated by one space, representing the number of objects and the initial length of the stick.

The next $n$ lines each contain three integers $x_{i}$, $y_{i}$, and $z_{i}$.

Note that $\left(x_{i}, y_{i}\right)=(0,0)$ may occur. Such points are considered to be touched immediately at the start.

Output Format

Output one line containing $n$ integers, with one space between adjacent integers, in order, representing the rank of each object.

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

1 1 3 4 -1

Hint

For $30\%$ of the testdata, $1 \leq n \leq 500$.

For $60\%$ of the testdata, $1 \leq n \leq 5000$.

For all testdata, $1 \leq n \leq 2\times10^5$, $-10^{9} \leq x_{i}, y_{i} \leq 10^{9}$, $1 \leq L, z_{i} \leq 10^{9}$.

This is Problem H of Lanqiao Cup 2022 Provincial Contest Group A.

Translated by ChatGPT 5