Казак Вус, секрет Леди и ведьма
Леди наконец решила раскрыть свой Новый Надсекретный Секрет (ННС) Казаку Усу, но и здесь не обошлось без приключений. Ведьма превратила Казака в маленького человечка и предложила ему сыграть в игру. Кстати, многие считают, что Леди сама является ведьмой и просто тянет время.
Ведьма переместила человечка в двумерное пространство, которое можно представить как первую четверть декартовой системы координат. В этом пространстве проведены горизонтальные отрезки, параллельные оси абсцисс, и вертикальные прямые, параллельные оси ординат. Обратите внимание, что отрезки имеют начало и конец, а прямые — нет.
Казак Ус может быть представлен как точка. Он может двигаться по горизонтальным отрезкам или вертикальным прямым, если его точка принадлежит соответствующему элементу. По горизонталям человечек может двигаться только вправо, а по вертикалям — вверх и вниз. Также, если человечек находится в самой правой точке одного из горизонтальных отрезков, он может прыгнуть вниз и двигаться, пока не встретит другой горизонтальный отрезок или не приземлится на ось абсцисс. Изначально Казак стоит в самой левой точке одного из горизонтальных отрезков. Когда он приземляется на ось абсцисс, игра заканчивается. Цель Казака — завершить игру в точке с наибольшей возможной абсциссой.
Чем быстрее ведьма отпустит Уса, тем скорее Леди расскажет свой ННС. Помогите Казаку и определите наибольшую возможную абсциссу, в которой он может завершить игру.
Формат входных данных
Первая строка содержит одно целое число n (1 ≤ n ≤ 100 000) — количество горизонтальных отрезков.
Вторая строка содержит одно целое число m (1 ≤ m ≤ 100 000) — количество вертикальных прямых.
Третья строка содержит одно целое число k (1 ≤ k ≤ n) — номер горизонтального отрезка, на начале которого стоит Казак Ус.
Следующие n строк содержат по три целых числа x[l], x[r], y (1 ≤ x[l] < x[r] ≤ 10^9, 1 ≤ y ≤ 10^9) — левая абсцисса, правая абсцисса и ордината очередного горизонтального отрезка. Гарантируется, что никакие два горизонтальных отрезка не имеют общих точек.
Следующая строка содержит m целых чисел x (1 ≤ x ≤ 10^9) — абсциссы вертикальных прямых. Гарантируется, что все прямые имеют разные координаты.
Формат выходных данных
В единственной строке выведите одно число — ответ на задачу.