Поездка на автобусе
Есть 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.