Stable Flight Path

You are flying from anchor point to anchor point using the "Wind Wings" along directed flight corridors. There are (N) anchors numbered (1,2,\ldots,N) and (M) directed flight corridors numbered (1,2,\ldots,M). For the (i)-th corridor, its starting anchor is (u_i) and its destination anchor is (v_i).

Each corridor (i) opens at time (O_i) and closes after time (C_i); that is, you may enter corridor (i) at any time (t) satisfying (O_i \le t \le C_i). Once you enter corridor (i) from anchor (u_i), you immediately arrive at anchor (v_i) and your arrival time becomes a random real number in the interval ([L_i, R_i]) (with equal probability for all values in the interval). Note that upon arriving at an anchor, you must instantly board the next corridor if you wish to continue your flight; otherwise, your flight ends at that moment.

You start at a given anchor (S) and wish to visit other anchors. For an arbitrary anchor (i) ((1\le i\le N)), a flight path is a sequence of corridors (E_1,E_2,\ldots,E_k) satisfying the following conditions:

1. \(E_1\) must depart from anchor \(S\) and \(E_k\) must arrive at anchor \(i\).
2. For every consecutive pair \(E_j\) and \(E_{j+1}\) (\(1\le j < k\)), the arrival anchor of \(E_j\) equals the departure anchor of \(E_{j+1}\).

A path is called a stable path if and only if, regardless of the random outcomes on each corridor, you can always complete the entire path. In other words, for every two consecutive corridors \(E_j\) and \(E_{j+1}\) (for \(j \ge 1\)), the entire arrival time interval of \(E_j\), namely \([L_{E_j}, R_{E_j}]\), must be contained in the departure time window of \(E_{j+1}\), i.e.,

\[ [L_{E_j},R_{E_j}] \subseteq [O_{E_{j+1}}, C_{E_{j+1}}]. \]

The arrival time of a stable path is defined as the latest possible arrival time at the destination anchor \(i\) (which is \(R_{E_k}\) for the last corridor \(E_k\)). For an anchor \(i\) (with \(i \neq S\)), define \(T_i\), the stable arrival time for anchor \(i\), as the minimum arrival time among all stable paths that reach \(i\). (If no stable path exists for anchor \(i\) or if \(i = S\), then we define \(T_i=0\).)

Your task is to compute the maximum value among \(T_1,T_2,\ldots,T_N\).

inputFormat

The first line contains three numbers (N), (M), and (S) (the number of anchors, the number of corridors, and the starting anchor).

Each of the following (M) lines contains six numbers: (u_i), (v_i), (O_i), (C_i), (L_i), and (R_i) describing a flight corridor. All time values are real numbers (or integers) satisfying the conditions in the statement.

outputFormat

Output a single number, which is the maximum stable arrival time among all anchors (T_1, T_2, \ldots, T_N).

sample

3 4 1
1 2 0 10 5 7
2 3 4 8 6 9
1 3 2 6 3 5
2 3 7 12 8 10

7