CF832C.Strange Radiation

n people are standing on a coordinate axis in points with positive integer coordinates strictly less than 106. For each person we know in which direction (left or right) he is facing, and his maximum speed.

You can put a bomb in some point with non-negative integer coordinate, and blow it up. At this moment all people will start running with their maximum speed in the direction they are facing. Also, two strange rays will start propagating from the bomb with speed s: one to the right, and one to the left. Of course, the speed s is strictly greater than people's maximum speed.

The rays are strange because if at any moment the position and the direction of movement of some ray and some person coincide, then the speed of the person immediately increases by the speed of the ray.

You need to place the bomb is such a point that the minimum time moment in which there is a person that has run through point 0, and there is a person that has run through point 106, is as small as possible. In other words, find the minimum time moment t such that there is a point you can place the bomb to so that at time moment t some person has run through 0, and some person has run through point 106.

有 $n$ 个人站在坐标轴上，各自位于严格小于 $10^6$ 的正整数坐标处。对每个人，我们知道他面朝的方向（向左或向右）及其最大速度。

你可以在某个非负整数坐标处放置一枚炸弹并引爆。此时，所有人将立即以其最大速度、按各自面朝的方向开始奔跑。同时，两条“奇异射线”将从炸弹位置以速度 $s$ 向左右两个方向传播（即一条向右，一条向左）。显然，射线速度 $s$ 严格大于所有人的最大速度。

这些射线之所以“奇异”，是因为：在任意时刻，若某条射线的位置与某个人的位置重合，且该射线的传播方向与该人的运动方向一致，则该人的速度会立即增加射线的速度 $s$（即其当前速度变为原速度加 $s$；此后若再次被同向射线追上，速度会再次增加 $s$，以此类推）。

你需要选择一个放置炸弹的位置，使得至少有一人跑过点 $0$ 且至少有一人跑过点 $10^6$ 这两个事件发生的最早时间尽可能小。换言之，求最小的时间 $t$，使得存在某个炸弹放置位置，满足：在时刻 $t$，已有某人经过了 $0$，同时已有（可能为另一人）某人经过了 $10^6$。

The first line contains two integers n and s (2 ≤ n ≤ 105, 2 ≤ s ≤ 106) — the number of people and the rays' speed.

The next n lines contain the description of people. The i-th of these lines contains three integers x__i, v__i and t__i (0 < x__i < 106, 1 ≤ v__i < s, 1 ≤ t__i ≤ 2) — the coordinate of the i-th person on the line, his maximum speed and the direction he will run to (1 is to the left, i.e. in the direction of coordinate decrease, 2 is to the right, i.e. in the direction of coordinate increase), respectively.

It is guaranteed that the points 0 and 106 will be reached independently of the bomb's position.

第一行包含两个整数 $n$ 和 $s$（$2 \leq n \leq 10^5$，$2 \leq s \leq 10^6$）—— 分别表示人数和射线的速度。

接下来的 $n$ 行描述了每个人的信息。其中第 $i$ 行包含三个整数 $x_i$、$v_i$ 和 $t_i$（$0 < x_i < 10^6$，$1 \leq v_i < s$，$1 \leq t_i \leq 2$）—— 分别表示第 $i$ 个人在数轴上的坐标、其最大速度，以及他将奔跑的方向（$1$ 表示向左，即坐标减小的方向；$2$ 表示向右，即坐标增大的方向）。

保证无论炸弹位于何处，点 $0$ 和 $10^6$ 均可被到达。

Print the minimum time needed for both points 0 and 106 to be reached.

Your answer is considered correct if its absolute or relative error doesn't exceed 10 - 6. Namely, if your answer is a, and the jury's answer is b, then your answer is accepted, if .

输出到达点 0 和点 10⁶ 所需的最短时间。

若您的答案的绝对误差或相对误差不超过 10⁻⁶，则视为正确。即，若您的答案为 a，评测机的标准答案为 b，则当满足 时，您的答案被接受。

In the first example, it is optimal to place the bomb at a point with a coordinate of 400000. Then at time 0, the speed of the first person becomes 1000 and he reaches the point 106 at the time 600. The bomb will not affect on the second person, and he will reach the 0 point at the time 500000.

In the second example, it is optimal to place the bomb at the point 500000. The rays will catch up with both people at the time 200. At this time moment, the first is at the point with a coordinate of 300000, and the second is at the point with a coordinate of 700000. Their speed will become 1500 and at the time 400 they will simultaneously run through points 0 and 106.

在第一个例子中，将炸弹放置在坐标为 $400000$ 的位置是最优的。此时，在时刻 $0$，第一个人的速度变为 $1000$，并在时刻 $600$ 到达点 $10^6$。炸弹不会影响第二个人，他将在时刻 $500000$ 到达点 $0$。

在第二个例子中，将炸弹放置在点 $500000$ 是最优的。射线将在时刻 $200$ 追上两个人。此时，第一个人位于坐标为 $300000$ 的点，第二个人位于坐标为 $700000$ 的点。他们的速度将变为 $1500$，并在时刻 $400$ 同时经过点 $0$ 和点 $10^6$。