题目背景

风带来故事的种子，时间使之神话。

题目描述

你在 $N$ 个锚点间，沿着 $M$ 条有向航道，使用风之翼进行飞行。锚点依次编号为 $1,2,\cdots,N$，有向航道依次编号为 $1,2,\cdots,M$。第 $i$ 条航道的出发锚点为 $u_i$，到达锚点为 $v_i$。

由于巴巴斯托与时间存在神秘的联系，第 $i$ 条航道将在时刻 $O_i$ 开启，在时刻 $C_i$ 后关闭。也就是说，对于任意的 $O_i \le t \le C_i$，你可以在时刻 $t$ 由锚点 $u_i$ 进入航道 $i$。进入航道后，空间上，你将直接到达锚点 $v_i$，时间上，时间将等概率的变化为 $[L_i,R_i]$ 中的一个实数对应的时刻。注意到达一个锚点后，你必须在同一时刻立刻进入下一段航道，否则你必须在此结束飞行。

你将从锚点 $S$ 出发，尝试访问锚点 $i(1\le i\le N)$，你需要对于锚点 $i$ 确定一条路径 $E_1,E_2,E_3,\cdots,E_k$，其中 $E_x(1\le x\le k)$ 表示一条航道。要求 $E_1$ 从锚点 $S$ 出发，$E_k$ 到达锚点 $i$，且对于 $1\le j<k$，满足 $E_j$ 的到达锚点与 $E_{j+1}$ 的出发锚点相同。一条路径是稳定路径，当且仅当无论每次通过航道后时间如何变化，都可以走完整条路径。一条稳定路径的到达时间是通过路径前往锚点 $i$ 时，最晚的可能到达锚点 $i$ 的时刻。访问锚点 $i$ 的稳定到达时间 $T_i(i \neq S)$ 是所有到达 $i$ 的稳定路径中到达时间的最小值。你可以在任意非负时刻出发。如果不存在访问锚点 $i$ 的稳定路径或 $i=S$，则 $T_i=0$。

请你求出 $T_i(1\le i\le N)$ 的最大值。

输入格式

输入共 $M+1$ 行。

输入的第一行为三个整数 $N,M,S$，分别表示锚点数、航道数和起点锚点。

接下来 $M$ 行，每行包含六个整数 $u_i,v_i,O_i,C_i,L_i,R_i$，描述了第 $i$ 条航道的有关信息，变量具体含义见题目描述部分。

输出格式

输出一行一个整数，表示 $T_i$ 的最大值。

4 10 1
4 2 6 20111 6 11900
2 4 2 10786 13 23576
2 1 3 5274 16 13903
2 1 2 17162 1 26120
1 2 1 42040 11 16065
2 1 4 23690 18 26541
2 3 9 18977 2 26795
4 1 4 51880 1 25060
1 4 13 17776 3 28236
1 4 1 19112 1 10131

26795

见选手目录下的 wind/wind2.in 与 wind/wind2.ans。

见选手目录下的 wind/wind3.in 与 wind/wind3.ans。

见选手目录下的 wind/wind4.in 与 wind/wind4.ans。

提示

样例解释 1

对于锚点 $1$，显然有 $T_1=0$。

对于锚点 $2$，沿路径 $1 \rightarrow 2$ ，$T_2=16065$。

对于锚点 $3$，沿路径 $1 \rightarrow 2 \rightarrow 3$ ，$T_3=26795$。

对于锚点 $4$，沿路径 $1 \rightarrow 4$ ，$T_4 = 10131$。

综上所述，答案 $\max T_i=T_3=26795$。

子任务

对于所有测试数据，保证 $1 \le N,M \le 5\times 10^5$，$1 \le O_i,L_i \le 20$，$1 \le O_i \le C_i \le 10^9$，$1 \le L_i \le R_i \le 10^9$，$1\le S \le N$。

特殊性质 A：一个锚点连接的航道数不超过 $100$。