Kozak Vus, the Secret of the Lady and the Witch
Lady has finally decided to disclose her New Ultra-Secret Secret (NUSS) to Cossack Vus, but not without some challenges. A witch has transformed Cossack Vus into a tiny figure and proposed a game. Rumor has it that the Lady herself might be the witch, merely buying time.
The witch has placed the tiny Cossack in a two-dimensional space, represented as the first quadrant of the Cartesian coordinate system. In this space, there are horizontal segments—parallel to the x-axis—and vertical lines—parallel to the y-axis. Note that segments have defined start and end points, whereas lines extend indefinitely.
Cossack Vus is represented as a point. He can traverse the horizontal segments or vertical lines if he is positioned on them. On the horizontals, he can only move to the right, while on the verticals, he can move both up and down. Additionally, if he reaches the rightmost end of a horizontal segment, he can jump down and continue moving until he encounters another horizontal segment or lands on the x-axis. Initially, Cossack Vus stands at the leftmost point of one of the horizontal segments. The game concludes when he lands on the x-axis, and his objective is to finish at the point with the highest possible x-coordinate.
The quicker the witch releases Vus, the sooner the Lady will unveil her NUSS. Assist the Cossack by determining the largest possible x-coordinate where he can end the game.
Input Format
The first line contains a single integer n (1 ≤ n ≤ 100,000) — the number of horizontal segments.
The second line contains a single integer m (1 ≤ m ≤ 100,000) — the number of vertical lines.
The third line contains a single integer k (1 ≤ k ≤ n) — the index of the horizontal segment where Cossack Vus initially stands.
The following n lines each contain three integers x[l], x[r], y (1 ≤ x[l] < x[r] ≤ 10^9, 1 ≤ y ≤ 10^9) — representing the left x-coordinate, right x-coordinate, and y-coordinate of each horizontal segment. It is guaranteed that no two horizontal segments overlap.
The next line contains m integers x (1 ≤ x ≤ 10^9) — the x-coordinates of the vertical lines. It is guaranteed that all vertical lines have distinct coordinates.
Output Format
Output a single number on a single line — the answer to the problem.