Background

The wind brings the seeds of stories, and time turns them into myths.

Problem Description

You are flying among $N$ anchor points along $M$ directed air routes using the Wings of Wind. The anchor points are numbered $1,2,\cdots,N$, and the directed routes are numbered $1,2,\cdots,M$. For route $i$, the starting anchor point is $u_i$, and the destination anchor point is $v_i$.

Due to Barbatos's mysterious connection with time, route $i$ opens at time $O_i$ and closes after time $C_i$. That is, for any $O_i \le t \le C_i$, you can enter route $i$ from anchor point $u_i$ at time $t$. After entering a route, spatially you will arrive directly at anchor point $v_i$. Temporally, the time will change with equal probability to a real-valued moment corresponding to some real number in $[L_i,R_i]$. Note that after arriving at an anchor point, you must immediately enter the next route at the same moment; otherwise, you must end the flight there.

You will start from anchor point $S$ and try to visit anchor point $i\ (1\le i\le N)$. You need to determine a path $E_1,E_2,E_3,\cdots,E_k$, where $E_x\ (1\le x\le k)$ denotes a route. The path must satisfy that $E_1$ starts from anchor point $S$, $E_k$ arrives at anchor point $i$, and for $1\le j<k$, the destination anchor point of $E_j$ is the same as the starting anchor point of $E_{j+1}$. A path is a stable path if and only if, no matter how the time changes after each route traversal, you can complete the entire path. The arrival time of a stable path is, when traveling to anchor point $i$ along this path, the latest possible moment at which you may arrive at anchor point $i$. The stable arrival time $T_i$ of anchor point $i\ (i \neq S)$ is the minimum among the arrival times of all stable paths that reach $i$. You may start at any non-negative time. If there is no stable path to visit anchor point $i$, or if $i=S$, then $T_i=0$.

Please compute the maximum value of $T_i\ (1\le i\le N)$.

Input Format

The input consists of $M+1$ lines.

The first line contains three integers $N,M,S$, representing the number of anchor points, the number of routes, and the starting anchor point.

The next $M$ lines each contain six integers $u_i,v_i,O_i,C_i,L_i,R_i$, describing route $i$. The meanings of the variables are given in the description.

Output Format

Output one line with one integer, representing the maximum value among $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。

Hint

Sample Explanation 1

For anchor point $1$, clearly $T_1=0$.

For anchor point $2$, along the path $1 \rightarrow 2$, $T_2=16065$.

For anchor point $3$, along the path $1 \rightarrow 2 \rightarrow 3$, $T_3=26795$.

For anchor point $4$, along the path $1 \rightarrow 4$, $T_4 = 10131$.

Therefore, the answer is $\max T_i=T_3=26795$.

Subtasks

For all testdata, it is guaranteed that $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$, and $1\le S \le N$.

Special Property A: The number of routes connected to a single anchor point does not exceed $100$.

Translated by ChatGPT 5