Поїздка автобусом
Є N міст і M односторонніх прямих автобусних маршрутів (без проміжних зупинок) між ними. Міста пронумеровані від 1 до N. Подорожній, який знаходиться в місті 1 в момент часу 0, повинен прибути в місто P. Його заберуть з автобусної станції в місті P точно в момент часу T. Якщо він прибуде раніше, йому доведеться чекати.
Для кожного автобусного маршруту i ми знаємо, звідки і куди він прямує, тобто міста s_i та t_i. Ми також знаємо час відправлення та прибуття, але лише приблизно: відомо, що автобус відправляється з s_i у межах [a_i, b_i] і прибуває в t_i у межах [c_i, d_i] (включно з кінцевими точками в обох випадках).
Подорожній не любить чекати, тому шукає план подорожі, який мінімізує максимальний можливий час очікування, при цьому гарантуючи, що він не пропустить пересадкові автобуси (тобто кожного разу, коли він змінює автобуси, найпізніше можливе прибуття вхідного автобуса не повинно бути пізніше найранішого можливого часу відправлення вихідного автобуса).
При підрахунку часу очікування ми повинні враховувати найраніший можливий час прибуття і найпізніший можливий час відправлення.
Напишіть програму, яка допоможе подорожньому знайти відповідний план.
Вхідні дані
Перший рядок містить цілі числа N (1 ≤ N ≤ 50000), M (1 ≤ M ≤ 100000), P (1 ≤ P ≤ N), та T (0 ≤ T ≤ 1000000000).
Наступні M рядків описують автобусні маршрути. Кожен рядок містить цілі числа s_i, t_i, a_i, b_i, c_i, d_i, де s_i та t_i - це початкове та кінцеве міста автобусного маршруту i, а a_i, b_i, c_i, d_i описують часи відправлення та прибуття, як пояснено вище (1 ≤ s_i ≤ N, 1 ≤ t_i ≤ N, 0 ≤ a_i ≤ b_i < c_i ≤ d_i ≤ 1000000000).
Вихідні дані
Єдиний рядок вихідного файлу повинен містити максимальний можливий загальний час очікування для найбільш підходящого можливого плану подорожі. Якщо неможливо гарантувати прибуття в місто P до часу T, рядок повинен містити –1.