在数轴上给定 $$$n$$$ 段,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 段涵盖从 $$$l_i$$$ 到 $$$r_i$$$ 的所有整数点,并具有值 $$$w_i$$$。
系统会要求您选择这些片段的子集(可能是全部)。一旦选择了子集,如果存在覆盖两个整数点的选定线段,则可以在两个整数点之间移动。如果可以从点 $$$1$$$ 开始以任意次数的移动到达点 $$$m$$$,则子集是好的。
子集的成本是其中段的最大值和最小值之间的差。找到一个好的子集的最小成本。
在每个测试中都至少存在一个好的子集。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$2 \le m \le 10^6$$$) — 段数和整数点数。
接下来的 $$$n$$$ 行包含三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$w_i$$$ ($$$1 \le l_i < r_i \le m$$$; $$$1 \le w_i \le 10^6$$$) — 第 $$$i$$$ 段的描述。
在每个测试中都至少存在一个好的子集。
输出
打印一个整数——一个好的子集的最小成本。
示例
输入 #1
5 12 1 5 5 3 4 10 4 10 6 11 12 5 10 12 3
输出 #1
3
输入 #2
1 10 1 10 23
输出 #2
0