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