Pinball

Time limit1sMemory limit128 MB

Summary

A ball falls straight down from x0 onto slanted segments, slides down each hit segment to its lower end, and the task asks for the final x coordinate.

Level: Medium7 of 10
Topics: Geometry, Sorting, Simulation
Solved: No attempts yet

Problem

Sunyoung is addicted to pinball. She can always hit the spot she aims for, but the ball bounces off the bumpers so many times that she cannot predict exactly where it lands.

So Sunyoung modeled the pinball table as a set of line segments and the ball as a point dropped from infinite height. The ball falls straight down until it meets a segment. Once it meets one, it slides along that segment down to the segment's lower endpoint, and from there it falls straight down again.

The endpoints of a segment belong to the segment. No two segments meet each other, and no endpoint of a segment lies on another segment. No segment is vertical or horizontal. The order in which the segments are given carries no meaning.

Input

The first line contains the number of segments $N$ . ( $0 \le N \le 100\,000$ )

Each of the next $N$ lines contains the coordinates of the two endpoints of one segment, $x_1$ $y_1$ $x_2$ $y_2$ . ( $-1\,000\,000 \le x_i, y_i \le 1\,000\,000$ )

The last line contains the x coordinate $x_0$ where the ball starts falling. ( $-1\,000\,000 \le x_0 \le 1\,000\,000$ )

All coordinates are integers.

Output

Print the final x coordinate of the ball on the first line. After the ball leaves the last segment it keeps falling straight down, so its x coordinate never changes again.

Examples3

Example 1
Input
```
2
-1 1 1 -1
1 -2 2 -3
0
```
Expected output
```
2
```
Example 2
Input
```
3
-1 1 1 -1
1 -2 0 -3
1 -3 2 -4
0
```
Expected output
```
0
```
Example 3
Input
```
0
7
```
Expected output
```
7
```