버스 여행

$N$개의 도시와, 이 도시들을 잇는 $M$개의 단방향 직행 버스 노선(중간 정차 없음)이 있다. 도시는 $1$번부터 $N$번까지 번호가 매겨져 있다. 한 여행자가 시각 $0$에 $1$번 도시에 있으며, $P$번 도시에 도착해야 한다. 누군가가 정확히 시각 $T$에 $P$번 도시의 버스 정류장에서 그를 데리러 온다. 더 일찍 도착하면 그만큼 기다려야 한다.

각 버스 노선 $i$에 대해 출발 도시 $s_i$와 도착 도시 $t_i$를 알고 있다. 출발 시각과 도착 시각도 알지만 정확하지 않고 범위로만 주어진다. 즉, 버스는 $s_i$에서 구간 $[a_i, b_i]$ 안의 어느 시각엔가 출발하고, $t_i$에는 구간 $[c_i, d_i]$ 안의 어느 시각엔가 도착한다(양 끝 포함).

여행자는 기다리는 것을 싫어하므로, 환승을 절대 놓치지 않음을 보장하면서 가능한 최대 총 대기 시간을 최소화하는 여행 계획을 찾으려 한다. 환승이 보장되려면, 버스를 갈아탈 때마다 도착하는 버스의 가장 늦은 도착 시각이 출발하는 버스의 가장 이른 출발 시각보다 늦지 않아야 한다.

대기 시간을 계산할 때는 항상 가장 이른 도착 시각과 가장 늦은 출발 시각을 가정한다.

여행자를 위한 적절한 계획을 찾는 프로그램을 작성하시오.

첫째 줄에 네 정수 $N$ ($1 \le N \le 50000$), $M$ ($1 \le M \le 100000$), $P$ ($1 \le P \le N$), $T$ ($0 \le T \le 10^9$)가 주어진다.

이어지는 $M$개의 줄에는 각 버스 노선이 여섯 정수 $s_i$, $t_i$, $a_i$, $b_i$, $c_i$, $d_i$로 주어진다. 여기서 $s_i$와 $t_i$는 출발 도시와 도착 도시이고, $a_i, b_i, c_i, d_i$는 위에서 설명한 출발·도착 시각 범위를 나타낸다 ($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$).

가장 적절한 여행 계획에서 가능한 최대 총 대기 시간을 한 줄에 출력한다. $P$번 도시에 시각 $T$까지 도착함을 보장할 수 없으면 대신 $-1$을 출력한다.