#2892. 强袭作战

内存限制:512 MiB 时间限制:50 Sec

题目描述

在一个没有冬马的世界里,经历了学园祭后的春希着急着想要见到心爱的雪菜。然而在排队想见雪菜的fans太多了,春希一时半会凑不到雪菜面前。
作为高帅富,这样的问题怎么能难倒春希?春希从武也手中拿到了取自金闪闪宝库里的多啦A梦的传话筒,并且给每一个排队的fans都发了一个传话筒。
于是现在有N个人排成一列,第一个人是雪菜,后面N个人是雪菜的fans。第Ifan能在他的左侧中选一个距离不超过L的人发出频率在[xi,yi]的音波,并且第Ifan也能接受频率在[xi,yi]的音波。特别的,雪菜能接受所有频率的音波。
春希有些话想通过传话筒告诉雪菜,他想选择一个人作为传话的起始点,但不知道选谁比较好,作为春希的好友的你,能告诉他答案吗?
传话的具体解释:第I个人能选择其左边的距离不超过L的一个人J,只要双方对应的区间有交集,那么第I个人就能将信息传达给J。然后J又可以继续找下一个人传达信息。传达一次信息要1单位时间。

输入格式

第一行两个正整数N、L。接下来N-1行,第i行包含了三个正整数xiyili,其中li表示第i个人距离雪菜有li的距离,满足li严格递增。

输出格式

 
总共N-1行,每行一个数分别表示2N号fan至少需要多少单位时间,雪菜才能收到信息,如果无法传到雪菜则输出-1

样例

样例输入


			
3 1
1 2 1
2 3 2

样例输出


			
1
2
【数据规模和约定】
30%的数据满足N <=20000;
100%的数据满足2 <=N<= 2.5*10^5、0<=xi,yi,li<=2*10^9,1<=L<=2*10^9,xi<=yi.

数据范围与提示