Description

In the plane, there are several line segments $L_i$ (not necessarily pairwise disjoint) that form one track after another. A droplet of liquid falls from above. If it encounters a track, it slides downward along the track and leaves the track from its lower end; while on a track, it is not affected by anything else. Otherwise, it falls straight down vertically. Determine the position from which the droplet finally exits the entire system.

I'm sure this problem won't stump you.

Input Format

The first line contains two integers $N$ and $S$, indicating there are $N$ segments, and the droplet starts falling from the position with x-coordinate $S$.

Each of the following $N$ lines contains four integers $x_{i1}$, $y_{i1}$, $x_{i2}$, $y_{i2}$ describing the endpoints of each segment. Note that each segment excludes its two endpoints; the liquid can pass through an endpoint without touching the segment.

Output Format

Output a single integer on one line: the final x-coordinate where the droplet falls out.

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

4

Hint

For $50\%$ of the testdata, $1\le N\le 100$, $|x|,|y|,|S| \le 500$.

For $100\%$ of the testdata, $1\le N\le 10^5$, $|x|,|y|,|S| \le 10^9$.

Translated by ChatGPT 5