Kazak Vus, Ledi və cadugərin sirri#9089
Ledi nəhayət Yeni Ən Gizli Sirrini (YƏGS) Kazak Bığa açıqlamağa qərar verdi, lakin burada da macəralar bitmədi. Cadugər Kazak Bığı kiçik bir adama çevirdi və onu bir oyuna çağırdı. Bir çoxları isə elə düşünür ki, Ledi özü də cadugərdir və sadəcə vaxt uzadır.
Cadugər kiçik adamı ikiölçülü bir məkana — Dekart koordinat sisteminin birinci rübünə yerləşdirdi. Bu məkanda üfüqi seqmentlər (x-oxuna paralel) və şaquli düz xətlər (y-oxuna paralel) vardır. Qeyd edin ki, seqmentlərin başlanğıcı və sonu var, ama düz xətlər sonsuzdur.
Kazak Bığ bir nöqtə kimi təsvir olunur. O, yalnız olduğu üfüqi seqment və ya şaquli düz xətdə hərəkət edə bilər. Üfüqi seqmentlərdə yalnız sağa doğru, şaquli xətlərdə isə həm yuxarı, həm də aşağı hərəkət edə bilir. Üstəlik, əgər o, üfüqi seqmentin ən sağ nöqtəsindədirsə, aşağı tullanıb başqa bir üfüqi seqmentə və ya -oxuna çatana qədər düşməyə davam edə bilər. Əvvəlcə Kazak üfüqi seqmentlərin birinin ən sol nöqtəsində başlayır. Oyun o, -oxuna çatdığı anda bitir. Məqsədi — mümkün olan ən böyük koordinatında oyunu bitirməkdir.
Cadugər Bığı nə qədər tez azad etsə, Ledi də YƏGS-ni o qədər tez açıqlayacaq. Kazaka kömək edin və onun oyunu bitirə biləcəyi ən böyük abssisi tapın.
Birinci sətrdə bir tam ədəd (1 \le n \le 100{,}000) — üfüqi seqmentlərin sayı verilir.
İkinci sətrdə bir tam ədəd (1 \le m \le 100{,}000) — şaquli düz xətlərin sayı verilir.
Üçüncü sətrdə bir tam ədəd (1 \le k \le n) — Kazak Bığın başladığı üfüqi seqmentin nömrəsi verilir.
Növbəti sətrin hər birində üç tam ədəd x_l, x_r, (1 \le x_l < x_r \le 10^9, 1 \le y \le 10^9) — uyğun üfüqi seqmentin sol son nöqtəsi, sağ son nöqtəsi və ordinatı verilir. Qarant olunur ki, heç bir iki üfüqi seqment kəsişmir.
Növbəti sətrdə tam ədəd (1 \le x \le 10^9) — şaquli düz xətlərin koordinatları verilir. Bütün koordinatlar müxtəlifdir.
Yeganə sətirdə cavabı — Kazak Bığın oyunu bitirə biləcəyi mümkün olan ən böyük koordinatını çap edin.
Nümunə 1
Nümunə 2