Козак Вус, секрет Ледi та вiдьма
Козак Вус, секрет Ледi та вiдьма
Ледi нарештi вирiшила розповiсти свiй Новий Надсекретний Секрет (ННС) Козаковi Вусу, але й тут не обiйшлося без пригод. Вiдьма перетворила Козака на маленького чоловiчка i запропонувала йому зiграти в гру. До речi, багато хто вважає, що Ледi сама є вiдьмою та просто тягне час.
Вiдьма перемiстила чоловiчка у двовимiрний простiр, що може бути представлений як перша чверть декартової системи координат. У цьому просторi проведено горизонталi — вiдрiзки, паралельнi осi абсцис i вертикалi — прямi, паралельнi осi ординат. Звернiть увагу на те, що вiдрiзки мають початок i кiнець, а прямi — нi.
Козак Вус може бути заданий, як точка. Вiн може рухатись по горизонталях чи вертикалях, якщо точка, якою вiн заданий, належить одному чи iншому вiдповiдно. По горизонталях чоловiчок може рухатись лише вправо, а по вертикалях вгору та вниз. Також, якщо чоловiчок стоїть в найправiшiй точцi однiєї з горизонталей, вiн може стрибнути вниз i рухатись, доки не зустрiне iншу горизонталь або не приземлиться на вiсь абсцис. Спочатку Козак стоїть в найлiвiшiй точцi однiєї з горизонталей. Коли вiн приземляється на вiсь абсцис — гра закiнчується. Мета Козака — закiнчити гру в точцi з найбiльш можливою абсцисою.
Чим швидше вiдьма вiдпустить Вуса, тим ранiше Ледi розповiсть свiй ННС. Допоможiть Козаковi та скажiть найбiльш можливу абсцису, в якiй вiн може закiнчити гру.
Формат вхiдних даних
Перший рядок мiстить одне цiле число n (1 ≤ n ≤ 100 000) — кiлькiсть горизонталей.
Другий рядок мiстить одне цiле число m (1 ≤ m ≤ 100 000) — кiлькiсть вертикалей.
Третiй рядок мiстить одне цiле число k (1 ≤ k ≤ n) — номер горизонталi, на початку якої стоїть Козак Вус.
Наступнi n рядкiв мiстять по три цiлi числа xl, xr, y (1 ≤ xl < xr ≤ 109, 1 ≤ y ≤ 109) — лiва абсциса, права абсциса та ордината чергової горизонталi. Гарантується, що жоднi два горизонтальнi вiдрiзки не мають спiльних точок.
Наступний рядок мiстить m цiлих чисел x (1 ≤ x ≤ 109) — абсциса чергової вертикалi. Гарантується, що всi прямi мають рiзнi координати.
Формат вихiдних даних
В єдиному рядку виведiть одне число — вiдповiдь на задачу.
6 4 6 8 14 5 11 16 11 3 9 14 2 10 13 7 12 3 1 5 7 15 13 6 4
16
10 7 5 23 69 79 73 87 23 32 63 29 21 70 39 19 65 20 24 38 54 27 52 75 51 57 93 35 73 40 83 87 70 51 14 80 75 58 87 37
87