题目描述

这里有 $n$ 座城镇和城镇之间的 $m$ 条巴士单行线（没有中间停靠站）；城镇从 $1$ 到 $n$ 标号。

一个旅行者在 $0$ 时刻位于 $1$ 号城镇，想要到达 $p$ 号城镇。

他将乘坐巴士在 $t$ 时刻到达 $p$ 号城镇。如果他早到了，他必须等待。

对于任意一条巴士路线 $i$，我们知道其中的起点城镇 $u_i$ 和目标城镇 $v_i$。

我们也同样知道路线的出发时间和到达时间，但仅仅是近似值：我们知道巴士离开起点城镇 $s_i$ 在时间范围 $[a_i, b_i]$ 内，且到达目标城镇 $t_i$ 在时间范围 $[c_i,d_i]$ 内(端点值包括在内)。

旅行者不喜欢等待，因此他要寻找一个旅行计划使得最大等待时间尽量小，同时保证绝对不会错过计划中的任何一辆巴士。（意思是，每次他换乘巴士，他需要下车的巴士的最晚到达时间不会迟于他需要搭乘的下一辆巴士的最早出发时间）

当计算等待时间时，我们必须假设最早可能到达的时间和最晚可能出发的时间。

编写一个程序，寻找一个最为合理的搭车计划。

输入格式

第一行四个整数 $n,m,p,t$。

接下来 $m$ 行，每行六个整数 $u_i,v_i,a_i,b_i,c_i,d_i$ 描述第 $i$ 条边。

输出格式

只需要包含一个数表示最合理搭车方案的最长可能等待时间。

如果不可能保证在 $t$ 时刻到达城市 $p$，那么输出 -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

32

数据规模与约定

对于 $100\%$ 的数据，$1\leq p\leq n\leq 5\times 10^4$，$1\leq m\leq 10^5$，$1\leq t\leq 10^9$。