Migrated from Lutece 863 Pinball

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Maria is quite addicted to pinball. She can shoot the ball to any position at the top of the board, but she cannot predict where the ball will end when it falls down, because it hits many bumpers on its way down.

She decided to model the pinball table as line segments and assume that the ball is a point that falls from infinite height. The ball falls straight vertically unless there is a segment immediately below it, in which case it follows the direction of the segment downwards until its end.

As you would expect the segments are closed, that is an endpoint is part of its segment. Pairs of segments do not intersect, not even at endpoints, and none is vertical or horizontal. Segments are not given in any specific order.

Input

The first line contains an integer $N$ $(0\leq N\leq 100 000)$, the number of segments. Then $N$ lines follow, each with four integers $x_1, y_1, x_2, y_2$, the coordinates of a segment $(-1 000 000\leq x_i,y_i\leq 1 000 000)$. The last line contains an integer $x_0$ $(-1 000 000\leq x_0\leq 1 000 000)$, the initial x-coordinate of the ball.

Output

Output a single integer $x_T$ , the final x-coordinate of the ball.

Samples

2
-1 1 1 -1
1 -2 2 -3
0

2

3
-1 1 1 -1
1 -2 0 -3
1 -3 2 -4
0

0

Note

Resources

Nordic Collegiate Programming Contest 2013