G. Platform Game
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Haha is playing a platform game.

One level of the game is about a robot falling among the platforms on a 2D map. Let's consider the 2D map as a coordinate system where the ground is the $$$x$$$-axis. Above the ground, there are $$$n$$$ platforms numbered from $$$1$$$ to $$$n$$$. All platforms are parallel to the ground, and the $$$i$$$-th platform can be viewed as a segment extending from $$$(l_i, y_i)$$$ to $$$(r_i, y_i)$$$, where the thickness of the platform is negligible. In the game, a robot initially spawns at point $$$(s_x, s_y)$$$. It'll move according to the following rules:

  • If the robot is on a platform, it will move toward the right until it leaves the platform. Note that we consider upon leaving the platform $$$i$$$, the $$$x$$$-coordinate of the robot will be $$$r_i$$$ (i.e. the right-border of the platform).
  • If the robot is not on any platform, it'll keep falling vertically until it either lands on a platform or finally lands on the ground.

Note that the robot can land on the $$$i$$$-th platform if and only if its $$$x$$$-coordinate is between $$$l_i$$$ and $$$r_i$$$ exclusively (i.e. $$$l_i \lt x \lt r_i$$$).

Now, Haha is curious about at which position the robot will land on the ground.

An example of how the robot will move among the given platforms
Input

The input contains multiple testcases.

The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 2\times 10^5$$$), denoting the number of testcases.

For each testcase:

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2\times 10^5$$$), denoting the number of platforms.

The $$$i$$$-th of the following $$$n$$$ lines contains three integers $$$l_i$$$, $$$r_i$$$, $$$y_i$$$ ($$$1 \leq l_i \lt r_i \leq 10^9$$$, $$$1 \leq y_i \leq 10^9$$$), denoting the position of the $$$i$$$-th platform.

The last line contains two integers $$$s_x$$$, $$$s_y$$$ ($$$1 \leq s_x, s_y \leq 10^9$$$), denoting the initial position of the robot.

It is guaranteed that no two platforms overlap with each other. Two platforms overlap when they share at least one common point.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\times 10^5$$$.

Output

For each testcase, output a single integer in one line, denoting the answer.

Example
Input
2
7
4 6 1
12 14 2
5 11 3
1 6 4
11 13 4
4 7 5
3 5 6
4 7
1
2 4 2
2 5
Output
11
2
Note

The first testcase of the example is illustrated as the picture above.

For the second testcase of the example, the robot will keep dropping without landing on any platform, until finally landing on the ground with the $$$x$$$-coordinate unchanged.