Description

大sz最近在玩一个由星球大战改编的游戏。话说绝地武士当前共控制了 $N$ 个星球。但是，西斯正在暗处悄悄地准备他们的复仇计划。绝地评议会也感觉到了这件事。于是，准备加派绝地武士到各星球防止西斯的突袭。一个星球受到攻击以后，会尽快通知到总基地。需要的时间越长的星球就需要越多绝地武士来防御。为了合理分配有限的武士，大sz需要你帮他求出每个星球各需要多少时间能够通知到总基地。由于某种原因，$N$ 个星球排成一条直线，编号 $1$ 至 $N$。其中总基地建在 $1$ 号星球上。每个星球虽然都是绝地武士控制的，但是上面居住的生物不一定相同，并且科技水平也不一样。第 $i$ 个星球能收到并分析波长在 $[x_i, y_i]$ 之间的信号，并且也能够发出在这个区间的信号，但是不能发出其他任何波长的信号。由于技术原因，每个星球只能发信号到比自己编号小的距离不超过 $L$ 的星球。特别地，强大的总基地可以接收任何波长的信号。每个星球处理接收到的数据需要 $1$ 个单位时间，传输时间可以忽略不计。求 $2$ 到 $N$ 号星球受到攻击以后至少需要多少单位时间，总基地能够处理好数据，如果无法传到总基地则输出 $-1$。

Input Format

第一行两个正整数 $N$、$L$。接下来 $N-1$ 行，总共第 $i$ 行包含了三个正整数 $x_i$、$y_i$、$l_i$，其中 $l_i$ 表示第 $i$ 个星球距离 $1$ 号星球 $l_i$ ，满足 $l_i$ 严格递增。

Output Format

总共 $N-1$ 行，每行一个数分别表示 $2$ 到 $N$ 号星球至少需要多少单位时间，总基地能够处理好数据，如果无法传到总基地则输出 $-1$。

Sample

Sample Input 1

3 1
1 2 1
2 3 2

Sample Output 1

1
2

Sample Input 2

3 3
1 2 1
2 3 2

Sample Output 2

1
1

Hints

30%的数据满足 $N \leq 20000$。

100%的数据满足 $2 \leq N \leq 2.5 \times 10^5、0\leq x_i，y_i，l_i \leq 2\times10^9，1\leq L\leq 2\times10^9,x_i \leq y_i$

Source

By 俞华程