Problem Background

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

Problem Description

You are flying using the Wind Glider between \( N \) anchor points along \( M \) directed routes. The anchor points are numbered \( 1, 2, \cdots, N \), and the directed routes are numbered \( 1, 2, \cdots, M \). The \( i \)-th route departs from anchor point \( u_i \) and arrives at anchor point \( v_i \).

Due to the mysterious connection between Babasto and time, the \( i \)-th route 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 \) at time \( t \) from anchor point \( u_i \). Upon entering the route, spatially, you will immediately arrive at anchor point \( v_i \), and temporally, the time will change to a moment randomly selected from the interval \([L_i, R_i]\). Note that once you arrive at an anchor point, you must immediately enter the next route at the same time, otherwise, you must end your flight.

You will start from anchor point \( S \) and attempt 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) \) represents a route. The path must start from anchor point \( S \) with \( E_1 \) and end at anchor point \( i \) with \( E_k \), and for \( 1 \le j < k \), the arrival anchor point of \( E_j \) must be the same as the departure anchor point of \( E_{j+1} \). A path is a stable path if and only if regardless of how the time changes after each route, the entire path can be completed. The arrival time of a stable path is the latest possible time to arrive at anchor point \( i \) using the path. The stable arrival time \( T_i (i \neq S) \) to visit anchor point \( i \) is the minimum arrival time among all stable paths to \( i \). You can start at any non-negative time. If there is no stable path to visit anchor point \( i \) or \( i = S \), then \( T_i = 0 \).

Please find 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 the information about the \( i \)-th route, with the specific meanings as described in the problem statement.

Output Format

Output a single integer, which is the maximum value of \( T_i \).

Sample Input and Output

Input Sample #1

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

Output Sample #1

26795

Notes/Hints

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 \).

In summary, the answer is \( \max T_i = T_3 = 26795 \).

Subtasks

For all test data, 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 \), \( 1 \le S \le N \).

Special Property A: The number of routes connected to an anchor point does not exceed \( 100 \).

见题面 Input 部分

见题面 Output 部分