大sz的游戏

大 sz 最近在玩一款由《星球大战》改编的游戏。绝地武士当前控制着 $N$ 个星球，但西斯正在暗中准备复仇计划。绝地评议会察觉后，决定向各个星球增派绝地武士，以防范西斯的突袭。

一个星球受到攻击后，会尽快将消息传递到总基地。通知总基地所需时间越长，该星球就需要部署越多的绝地武士。为了合理分配有限的武士，你需要求出每个星球将消息传递到总基地，并由总基地处理完毕所需的最短时间。

由于某种原因，$N$ 个星球排列在一条直线上，编号为 $1$ 至 $N$，总基地位于 $1$ 号星球。

不同星球上的生物种类和科技水平可能不同。第 $i$ 个星球能够接收、分析并发出波长位于区间 $[x_i,y_i]$ 内的信号，但不能发出其他波长的信号。特别地，总基地能够接收任意波长的信号。

由于技术限制，每个星球只能向编号比自己小，且与自己距离不超过 $L$ 的星球发送信号。每个星球处理接收到的数据需要 $1$ 个单位时间，信号的传输时间可以忽略不计。

输入格式

第一行包含两个正整数 $N$、$L$。

接下来 $N-1$ 行，第 $k$ 行（$1\le k\le N-1$）包含三个非负整数 $x_{k+1}$、$y_{k+1}$、$l_{k+1}$，分别表示编号为 $k+1$ 的星球能够收发的信号波长区间 $[x_{k+1},y_{k+1}]$，以及该星球到 $1$ 号星球的距离。

保证 $l_2<l_3<\cdots<l_N$。

输出格式

输出共 $N-1$ 行，依次表示编号为 $2$ 至 $N$ 的每个星球发送的数据至少需要多少个单位时间才能由总基地处理完毕。

如果某个星球的数据无法传递到总基地，则输出 $-1$。

样例输入

3 1
1 2 1
2 3 2

样例输出

1
2

数据范围

• 对于 $30\%$ 的数据，$N\le 2\times 10^4$；
• 对于 $100\%$ 的数据，$2\le N\le 2.5\times 10^5$；
• $0\le x_i,y_i,l_i\le 2\times 10^9$；
• $1\le L\le 2\times 10^9$；
• $x_i\le y_i$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3 1
1 2 1
2 3 2

输出

1
2