Kazak Vus, Ledi və cadugərin sirri
Ledi nəhayət öz Yeni Ən Gizli Sirrini (YƏGS) Kazak Bığa danışmağa qərar verdi, amma burada da macəralar olmadan keçinmədi. Cadugər Kazakı kiçik bir kişiyə çevirdi və ona oyun təklif etdi. Bu arada, bir çoxları düşünür ki, Ledi özü də cadugərdir və sadəcə vaxt uzadır.
Cadugər kişini Dekart koordinat sisteminin birinci rübü kimi təqdim edilə bilən ikiölçülü məkana köçürdü. Bu məkanda üfüqi xətlər — absis oxuna paralel olan seqmentlər və şaquli xətlər — ordinat oxuna paralel olan düz xətlər çəkilmişdir. Qeyd edək ki, seqmentlərin başlanğıcı və sonu var, amma düz xətlərin yoxdur.
Kazak Bığ bir nöqtə kimi təyin edilə bilər. O, üfüqi və ya şaquli xətlər boyunca hərəkət edə bilər, əgər o, təyin edildiyi nöqtə müvafiq olaraq birinə və ya digərinə aiddirsə. Üfüqi xətlər boyunca kişi yalnız sağa, şaquli xətlər boyunca isə yuxarı və aşağı hərəkət edə bilər. Həmçinin, əgər kişi üfüqi xətlərdən birinin ən sağ nöqtəsində dayanırsa, o, aşağı tullanıb başqa bir üfüqi xəttə rast gələnə və ya absis oxuna enənə qədər hərəkət edə bilər. Əvvəlcə Kazak üfüqi xətlərdən birinin ən sol nöqtəsində dayanır. O, absis oxuna enəndə oyun bitir. Kazakın məqsədi oyunu mümkün olan ən böyük absis nöqtəsində bitirməkdir.
Cadugər Bığı nə qədər tez buraxsa, Ledi öz YƏGS-ni bir o qədər tez danışacaq. Kazaka kömək edin və onun oyunu bitirə biləcəyi ən böyük absis nöqtəsini deyin.
Giriş formatı
Birinci sətir bir tam ədəd n (1 ≤ n ≤ 100 000) — üfüqi xətlərin sayını ehtiva edir.
İkinci sətir bir tam ədəd m (1 ≤ m ≤ 100 000) — şaquli xətlərin sayını ehtiva edir.
Üçüncü sətir bir tam ədəd k (1 ≤ k ≤ n) — Kazak Bığın dayandığı üfüqi xəttin nömrəsini ehtiva edir.
Növbəti n sətir hər biri üç tam ədəd x[l], xr, y (1 ≤ x[l] < x[r] ≤ 10^9, 1 ≤ y ≤ 10^9) — növbəti üfüqi xəttin sol absisi, sağ absisi və ordinatını ehtiva edir. Zəmanət verilir ki, heç bir iki üfüqi seqmentin ortaq nöqtəsi yoxdur.
Növbəti sətir m tam ədəd x (1 ≤ x ≤ 10^9) — növbəti şaquli xəttin absisini ehtiva edir. Zəmanət verilir ki, bütün xətlərin koordinatları fərqlidir.
Çıxış formatı
Tək sətirdə məsələnin cavabını verin.