有 $N$ 个城镇和 $M$ 条它们之间的单向直达公交线路（无中途停靠站）。城镇从 $1$ 到 $N$ 进行编号。一名旅行者在时刻 $0$ 位于城镇 $1$，他需要前往城镇 $P$。他将在时刻 $T$ 准时在城镇 $P$ 的公交站被接走。如果他提前到达，他将不得不等待。

对于每条公交线路 $i$，我们显然知道其起点城镇 $s_i$ 和终点城镇 $t_i$。我们还知道其出发和到达时间，但只是近似的：我们知道该公交车从 $s_i$ 出发的时刻在区间 $[a_i, b_i]$ 内，到达 $t_i$ 的时刻在区间 $[c_i, d_i]$ 内（两个区间均包含端点）。

旅行者不喜欢等待，因此他希望寻找一个旅行计划，在保证不会错过换乘公交的前提下，使最大可能的总等待时间最小。不会错过换乘公交意味着：每次他换乘公交时，前一辆车的最新可能到达时间不能晚于后一辆车的最早可能出发时间（即对于前一辆车 $u$ 和后一辆车 $v$，必须满足 $d_u \le a_v$）。

在计算等待时间时，我们必须假设最坏的情况，即前一辆车在最早可能的时间到达，而后一辆车在最晚可能的时间出发。

请编写一个程序，帮助旅行者找到一个最合适的旅行计划。

输入格式

第一行包含四个整数 $N$ ($1 \le N \le 50,000$)，$M$ ($1 \le M \le 100,000$)，$P$ ($1 \le P \le N$) 和 $T$ ($0 \le T \le 1,000,000,000$)。

接下来的 $M$ 行描述公交线路。每行包含六个整数 $s_i, t_i, a_i, b_i, c_i, d_i$，其中 $s_i$ 和 $t_i$ 是公交线路 $i$ 的起点和终点城镇，$a_i, b_i, c_i, d_i$ 如上文所述描述出发和到达时间（$1 \le s_i \le N$，$1 \le t_i \le N$，$0 \le a_i \le b_i < c_i \le d_i \le 1,000,000,000$）。

输出格式

输出唯一的一行，包含最合适的旅行计划下，最大可能的总等待时间。如果无法保证在时刻 $T$ 之前到达城镇 $P$，则输出 -1。

样例

输入样例 1

3 6 2 100
1 3 10 20 30 40
3 2 32 35 95 95
1 1 1 1 7 8
1 3 8 8 9 9
2 2 98 98 99 99
1 2 0 0 99 101

输出样例 1

32

输入样例 2

3 2 2 100
1 3 0 0 49 51
3 2 50 51 100 100

输出样例 2

-1

说明

对于样例 1，最优旅行计划在最悲观情况下的具体行程如下：

• 时刻 0...1：在城镇 1 等待（等待时间：$1 - 0 = 1$）
• 时刻 1...7：乘坐公交线路 3 从城镇 1 到城镇 1
• 时刻 7...8：在城镇 1 等待（等待时间：$8 - 7 = 1$）
• 时刻 8...9：乘坐公交线路 4 从城镇 1 到城镇 3
• 时刻 9...35：在城镇 3 等待（等待时间：$35 - 9 = 26$）
• 时刻 35...95：乘坐公交线路 2 从城镇 3 到城镇 2
• 时刻 95...98：在城镇 2 等待（等待时间：$98 - 95 = 3$）
• 时刻 98...99：乘坐公交线路 5 从城镇 2 到城镇 2
• 时刻 99...100：在城镇 2 等待（等待时间：$100 - 99 = 1$）

总等待时间：$1 + 1 + 26 + 3 + 1 = 32$。