_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.
## Input
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.
## Output
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 .
[samples]
## Note
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.
#cf_span[n] 个人站在一个坐标轴上，他们的位置是严格小于 #cf_span[106] 的正整数坐标。对于每个人，我们知道他面向的方向（左或右）以及他的最大速度。
你可以在某个非负整数坐标处放置一个炸弹并引爆它。此时，所有人将立即以他们的最大速度朝他们面向的方向奔跑。同时，两条奇异的射线将从炸弹出发，以速度 #cf_span[s] 向左右两个方向传播。显然，速度 #cf_span[s] 严格大于人的最大速度。
这些射线是奇异的：如果在任意时刻，某条射线的位置和某个行人当前的位置与移动方向完全一致，则该行人的速度会立即增加射线的速度。
你需要放置炸弹，使得满足以下条件的最小时间点尽可能小：存在一个人已经经过点 #cf_span[0]，同时存在另一个人已经经过点 #cf_span[106]。换句话说，找出最小的时间点 #cf_span[t]，使得存在一个炸弹放置位置，使得在时间 #cf_span[t] 时，某个人经过了 #cf_span[0]，另一个人经过了 #cf_span[106]。
第一行包含两个整数 #cf_span[n] 和 #cf_span[s]（#cf_span[2 ≤ n ≤ 105]，#cf_span[2 ≤ s ≤ 106]）——人数和射线的速度。
接下来的 #cf_span[n] 行描述每个人的信息。第 #cf_span[i] 行包含三个整数 #cf_span[xi]、#cf_span[vi] 和 #cf_span[ti]（#cf_span[0 < xi < 106]，#cf_span[1 ≤ vi < s]，#cf_span[1 ≤ ti ≤ 2]）——第 #cf_span[i] 个人的坐标、他的最大速度以及他奔跑的方向（#cf_span[1] 表示向左，即坐标减小的方向；#cf_span[2] 表示向右，即坐标增大的方向）。
保证无论炸弹放在何处，点 #cf_span[0] 和 #cf_span[106] 都会被到达。
输出使两个点 #cf_span[0] 和 #cf_span[106] 都被到达所需的最小时间。
你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被认为是正确的。即，若你的答案是 #cf_span[a]，评测标准答案是 #cf_span[b]，则当 时你的答案会被接受。
在第一个例子中，最优方案是将炸弹放在坐标 #cf_span[400000] 处。此时，在时间 #cf_span[0]，第一个人的速度变为 #cf_span[1000]，并在时间 #cf_span[600] 到达点 #cf_span[106]。炸弹不会影响第二个人，他在时间 #cf_span[500000] 到达 #cf_span[0] 点。
在第二个例子中，最优方案是将炸弹放在坐标 #cf_span[500000] 处。射线将在时间 #cf_span[200] 追上两个人。此时，第一个人位于坐标 #cf_span[300000]，第二个人位于坐标 #cf_span[700000]。他们的速度将变为 #cf_span[1500]，并在时间 #cf_span[400] 同时经过点 #cf_span[0] 和 #cf_span[106]。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[s]（#cf_span[2 ≤ n ≤ 105]，#cf_span[2 ≤ s ≤ 106]）——人数和射线的速度。接下来的 #cf_span[n] 行描述每个人的信息。第 #cf_span[i] 行包含三个整数 #cf_span[xi]、#cf_span[vi] 和 #cf_span[ti]（#cf_span[0 < xi < 106]，#cf_span[1 ≤ vi < s]，#cf_span[1 ≤ ti ≤ 2]）——第 #cf_span[i] 个人的坐标、他的最大速度以及他奔跑的方向（#cf_span[1] 表示向左，即坐标减小的方向；#cf_span[2] 表示向右，即坐标增大的方向）。保证无论炸弹放在何处，点 #cf_span[0] 和 #cf_span[106] 都会被到达。
## Output
输出使两个点 #cf_span[0] 和 #cf_span[106] 都被到达所需的最小时间。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被认为是正确的。即，若你的答案是 #cf_span[a]，评测标准答案是 #cf_span[b]，则当 时你的答案会被接受。
[samples]
## Note
在第一个例子中，最优方案是将炸弹放在坐标 #cf_span[400000] 处。此时，在时间 #cf_span[0]，第一个人的速度变为 #cf_span[1000]，并在时间 #cf_span[600] 到达点 #cf_span[106]。炸弹不会影响第二个人，他在时间 #cf_span[500000] 到达 #cf_span[0] 点。
在第二个例子中，最优方案是将炸弹放在坐标 #cf_span[500000] 处。射线将在时间 #cf_span[200] 追上两个人。此时，第一个人位于坐标 #cf_span[300000]，第二个人位于坐标 #cf_span[700000]。他们的速度将变为 #cf_span[1500]，并在时间 #cf_span[400] 同时经过点 #cf_span[0] 和 #cf_span[106]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of people, and $ s \in \mathbb{R}^+ $ be the speed of the rays ($ s > v_i $ for all $ i $).
Let $ P = \{ (x_i, v_i, t_i) \mid i \in \{1, \dots, n\} \} $ be the set of people, where:
- $ x_i \in \mathbb{R} $ is the initial position ($ 0 < x_i < 10^6 $),
- $ v_i \in \mathbb{R}^+ $ is the maximum speed ($ 1 \le v_i < s $),
- $ t_i \in \{1, 2\} $ is the direction: $ t_i = 1 $ means left (toward 0), $ t_i = 2 $ means right (toward $ 10^6 $).
Let $ b \in \mathbb{R}_{\ge 0} $ be the position of the bomb.
**Constraints**
1. $ 2 \le n \le 10^5 $
2. $ 2 \le s \le 10^6 $
3. $ 0 < x_i < 10^6 $, $ 1 \le v_i < s $, $ t_i \in \{1,2\} $ for all $ i $
4. The bomb position $ b $ is a non-negative real number.
5. The rays propagate at speed $ s $: one leftward ($ -s $), one rightward ($ +s $) from $ b $.
6. When a ray and a person meet (same position at same time), the person’s speed becomes $ v_i + s $ for the remainder of their motion.
**Objective**
Find the minimal time $ T^* $ such that there exists a bomb position $ b \ge 0 $ for which:
- At time $ T^* $, at least one person has reached position $ 0 $,
- At time $ T^* $, at least one person has reached position $ 10^6 $.
For each person $ i $:
- If $ t_i = 1 $ (left-moving), define $ T_i(b) $ as the time to reach 0, accounting for possible speed-up by the leftward ray.
- If $ t_i = 2 $ (right-moving), define $ T_i(b) $ as the time to reach $ 10^6 $, accounting for possible speed-up by the rightward ray.
For a fixed $ b $, define:
- $ T_{\text{left}}(b) = \min \{ T_i(b) \mid t_i = 1 \} $ — earliest time any left-moving person reaches 0,
- $ T_{\text{right}}(b) = \min \{ T_i(b) \mid t_i = 2 \} $ — earliest time any right-moving person reaches $ 10^6 $,
- $ T(b) = \max(T_{\text{left}}(b), T_{\text{right}}(b)) $ — time until both targets are reached.
Then:
$$
T^* = \min_{b \ge 0} T(b)
$$
**Note:** For each person $ i $, the time to reach their target depends on whether the ray from $ b $ catches them before they reach their target.
- For a left-moving person $ i $:
Let $ \tau_i(b) $ be the time when the leftward ray from $ b $ meets person $ i $.
Solve: $ x_i - v_i \tau = b - s \tau \Rightarrow \tau_i(b) = \frac{b - x_i}{s - v_i} $, if $ b \ge x_i $ and $ \tau_i(b) \ge 0 $.
If $ \tau_i(b) $ exists and $ \tau_i(b) \le \frac{x_i}{v_i} $, then the person’s speed becomes $ v_i + s $ after $ \tau_i(b) $, and the remaining distance to 0 is $ x_i - v_i \tau_i(b) $, covered in $ \frac{x_i - v_i \tau_i(b)}{v_i + s} $.
Total time: $ T_i(b) = \tau_i(b) + \frac{x_i - v_i \tau_i(b)}{v_i + s} $.
If the ray never catches them (i.e., $ b < x_i $), then $ T_i(b) = \frac{x_i}{v_i} $.
- For a right-moving person $ i $:
Solve: $ x_i + v_i \tau = b + s \tau \Rightarrow \tau_i(b) = \frac{x_i - b}{s - v_i} $, if $ b \le x_i $ and $ \tau_i(b) \ge 0 $.
If caught, remaining distance to $ 10^6 $: $ 10^6 - x_i - v_i \tau_i(b) $, covered at speed $ v_i + s $.
Total time: $ T_i(b) = \tau_i(b) + \frac{10^6 - x_i - v_i \tau_i(b)}{v_i + s} $.
If not caught ($ b > x_i $), then $ T_i(b) = \frac{10^6 - x_i}{v_i} $.
Thus, $ T^* = \min_{b \ge 0} \max\left( \min_{i: t_i=1} T_i(b), \min_{i: t_i=2} T_i(b) \right) $