You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

O 为什么会在 Y 后面？

题目描述

最后灰姑娘计划在里泰尔德剧院开启的那一刻，OIER 的机动小队也开始了他们的行动。

他们打算首先传送到起点，然后占领整个爱丽丝树^[1]，而最重要的目标就是到达编号为 $T$ 的核心结点。然而经过拓扑结构的转换，爱丽丝树已经变成了它的商空间——一条链，而且在它之上的行动也变得异常不稳定。

经过研究他们发现，这条链上依然有 $n$ 个结点^[2]，他们将这些结点按顺序用 $1,2,\dots,n$ 重新编号。然而，从编号为 $i$ 的结点出发，一个单位时间内能且仅能够到达编号为$[L_i,R_i]$的结点。不仅如此，爱丽丝树上的时间变得离散，以至于将从$S$ 出发视为第零个时刻，每一个正整数时刻他们都会被强制传送；在编号为 $i$ 的结点时会被传送到编号为 $a_i$ 的结点，传送可以看作瞬间进行。被传送一次之后，这个时刻他们就不会再次被传送。同时，传送之后他们必须再次出发，因为 OIER 小队的责任不允许他们留在原地。

就在机动小队计算出行动计划之后，不幸的事情发生了——他们的起点信息也因为拓扑结构陷入混乱，也就是说，他们将有可能从任何一个结点出发。

机动小队的作战将是灰姑娘掌控全城的一个重要环节，因此不能有失。你必须要计算出从每个结点出发到达 $T$ 的最短时间。注意，只有传送之后的到达才被看作有效。

数据格式与约定

输入

输入第一行包含 $2$ 个整数 $n,T(1 \le T \le n \le 10^5)$，表示结点个数和目标地点。

接下来 $n$ 行，每行包含 $3$ 个整数 $L_i,R_i,a_i(i=1,2,3,\dots,n,\forall i,1 \le L_i\le R_i \le n,1\le a_i\le n)$，表示从 $i$ 出发，经过一个单位时间能够到达编号为$[L_i,R_i]$的结点；而在正整数时刻到达 $i$ 时会被传送至 $a_i$。

输出

输出包含 $n$ 行，每行一个整数 $ans_i$，表示从结点 $i$ 到达 $T$ 的最小时间；如果从这个结点无论如何也无法到达 $T$，该行输出 $-1$。

样例

3 3
1 2 2
2 3 1
1 3 3

2
1
0

后记

2077 年 2 月 1 日。赛博朋克依旧没有到来。

里泰尔德的夜晚是黏稠的，黑暗被随处可见的泛光灯侵蚀，却又裹挟着这俗套至极的处处喧嚣。55 年过去，没有彻底的两极分化，没有绝望的 high tech low life，但散落在这个城市的，是那些曾经在小说里一次次出现、一遍遍重复的情节。

……你说 OIER？他们连来过的痕迹都没有留下。没有人记得他们。

里泰尔德剧院已经没有人了。除了常明的安全灯，没有任何一处还存在光芒。

安全灯之下，有一张小小的纸条。纸条大概是从日记本上撕下来的，纸张的颜色是染料染成的黄。上面只留着一行小字：

"Mans' cHarAdes is LeukeMia unfit' stanZa."

这就是他们的故事了。他们倾尽全力也没能改变的，一个俗套的故事。——不仅没改变故事，也没改变自己。

那么，现在，我们是不是应该聊聊……你的故事？