Bus Trip

There are $N$ towns and $M$ one-way direct bus routes (with no intermediate stops) connecting them. The towns are numbered from $1$ to $N$. A traveler is in town $1$ at time $0$ and must reach town $P$. Someone will meet him at the bus station in town $P$ at exactly time $T$; if he arrives earlier, he has to wait.

For each bus route $i$ we know its source town $s_i$ and destination town $t_i$. We also know its departure and arrival times, but only approximately: the bus departs from $s_i$ at some moment in the range $[a_i, b_i]$ and arrives at $t_i$ at some moment in the range $[c_i, d_i]$ (both endpoints included).

The traveler dislikes waiting, so he wants a travel plan that minimizes the maximum possible total waiting time while still guaranteeing that he never misses a connection. A connection is guaranteed only if, whenever he changes buses, the latest possible arrival time of the incoming bus is no later than the earliest possible departure time of the outgoing bus.

When computing waiting time, always assume the earliest possible arrival time and the latest possible departure time.

Write a program that finds a suitable plan for the traveler.

The first line contains four integers $N$ ($1 \le N \le 50000$), $M$ ($1 \le M \le 100000$), $P$ ($1 \le P \le N$), and $T$ ($0 \le T \le 10^9$).

Each of the next $M$ lines describes one bus route with six integers $s_i$, $t_i$, $a_i$, $b_i$, $c_i$, $d_i$, where $s_i$ and $t_i$ are the source and destination towns and $a_i, b_i, c_i, d_i$ describe the departure and arrival ranges as explained above ($1 \le s_i \le N$, $1 \le t_i \le N$, $0 \le a_i \le b_i < c_i \le d_i \le 10^9$).

Print a single line with the maximum possible total waiting time of the best travel plan. If it is impossible to guarantee arrival in town $P$ by time $T$, print $-1$ instead.