Description

声波（Sound Wave或Acoustic Wave）是声音的传播形式。声波是一种机械波，由物体（声源）振动产生，声波传

播的空间就称为声场。在气体和液体介质中传播时是一种纵波，但在固体介质中传播时可能混有横波。人耳可以听

到的声波的频率一般在20赫兹至20000赫兹之间。不同动物和不同的人能听到的声波频率都不一样。这里就不上图

了。现在，sg在和妹子玩一个很好玩的游戏。sg站在1号点，后面有他的n-1个小弟。现在妹子想告诉sg一些话，但

是她不知道选谁。由于sg的小弟们构造奇特，他们能听到的声波频率也是不一样的。第i个人可以发出并接收声波

频率为[xi,yi]的声音，并且每个人的声音最多只能传播不超过l的距离。每一次说话并被另一个人接收到的过程都

要消耗1单位时间。现在给出所有人能发出并接收的声波频率的范围和位置，sg的妹子想知道，每个小弟传话给sg

要多久。由于sg很牛逼，他可以接收所有小弟发出的声波，当然前提要在距离之内。sg的位置为0。

Format

Input

第一行：n，l，含义见题意。

第二行至第n行：xi，yi，li，[xi,yi]是第i个小弟能发出并接收的声波频率范围，li是第i个小弟的位置。

1≤n≤250000，0≤xi,yi,li≤2000000000，1≤l≤2000000000，xi≤yi。保证li单调递增

Output

第一行至第n-1行：第i行表示第i+1个小弟要传话给sg所消耗的时间。

Samples

3 1
1 2 1
2 3 2
1 1
0 0
0 2

1
2