eolymp
bolt
Try our new interface for solving problems
Problems

Pinball

Pinball

Time limit 1 second
Memory limit 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.

Input data

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 data

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

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

Examples

Input example #1
2
-1 1 1 -1
1 -2 2 -3
0
Output example #1
2
Source ACM ICPC NCPC 2013, 5th October 2013