eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків

Pinball

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

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.

Вхідні дані

The first line contains an integer N (0N100000), 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 (-1000000x_i, y_i1000000). The last line contains an integer x_0 (-1000000x_01000000), the initial x-coordinate of the ball.

Вихідні дані

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

Figure 1: Sample input 1 Figure 2: Sample input 2

Приклад

Вхідні дані #1
2
-1 1 1 -1
1 -2 2 -3
0
Вихідні дані #1
2
Джерело ACM ICPC NCPC 2013, 5th October 2013