Avtobus Səyahəti#3017
şəhər və onların arasında bir tərəfli, birbaşa avtobus marşrutu var (aralıq dayanacaqlar yoxdur). Şəhərlər -dən -ə qədər nömrələnib. Səyyah zamanı -ci şəhərdə yerləşir və -ci şəhərə çatmalıdır. O, -ci şəhərdəki avtobus stansiyasından məhz vaxtında götürüləcək. Əgər tez gəlsə, gözləməli olacaq.
Hər bir avtobus marşrutu üçün başlanğıc və son şəhərlər s_i və t_i verilib. Bundan əlavə, avtobusun start və bitmə vaxtları yalnız təxmini məlumdur: avtobus s_i-dən [a_i, b_i] intervalında çıxır, t_i-yə isə [c_i, d_i] intervalında çatır (hər iki halda uç nöqtələr də interavala daxildir).
Səyyah gözləməyi sevmir və buna görə elə bir səfər planı axtarır ki, həm əlaqə dəyişmələrində növbəti avtobusa gecikməsin (yəni, hər dəfə avtobus dəyişərkən, əvvəlki avtobusun maksimum gəliş vaxtı növbəti avtobusun minimum çıxış vaxtından gec olmasın), həm də maksimal ola biləcək gözləmə vaxtı mümkün qədər az olsun.
Gözləmə vaxtını hesablamaq üçün ən erkən mümkün çatma vaxtı və ən gec bilet alma vaxtı nəzərə alınmalıdır.
Səyyaha uyğun plan tapmaq üçün proqram yazın.
Birinci sətirdə (1 \leq N \leq 50000), (1 \leq M \leq 100000), (1 \leq P \leq N) və (0 \leq T \leq 1000000000) tam ədədləri verilir.
Növbəti sətirin hər biri bir avtobus marşrutunu təsvir edir. Hər sətirdə s_i, t_i, a_i, b_i, c_i, d_i ədədləri verilir; burada s_i və t_i — marşrutun başlanğıc və son şəhərləri, a_i, b_i, c_i, d_i isə yuxarıda izah olunduğu kimi çıxış və çatma vaxtlarından bəhs edir (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).
Çıxışa uyğun sətrdə, ən uyğun səfər planı üçün maksimal ola biləcək ümumi gözləmə vaxtını çıxarın. Əgər vaxtına qədər -yə çatmaq mümkün deyilsə, **–1** çap edin.
Nümunə 1