Пинбол
Мария очень увлечена пинболом. Она может запустить шарик в любую позицию в верхней части доски, но не может предсказать, где шарик окажется, когда он упадет, потому что он сталкивается с множеством буферов на своем пути вниз.
Она решила смоделировать стол для пинбола как набор отрезков и предположить, что шарик — это точка, которая падает с бесконечной высоты. Шарик падает строго вертикально, если только под ним нет отрезка, в этом случае он следует направлению отрезка вниз до его конца.
Как и ожидалось, отрезки замкнуты, то есть конечная точка является частью своего отрезка. Пары отрезков не пересекаются, даже в конечных точках, и ни один из них не является вертикальным или горизонтальным. Отрезки не даны в каком-либо определенном порядке.
Входные данные
Первая строка содержит целое число N (0 ≤ N ≤ 100000), количество отрезков. Затем следуют N строк, каждая с четырьмя целыми числами x_1 y_1 x_2 y_2, координатами отрезка (-1000000 ≤ x_i, y_i ≤ 1000000). Последняя строка содержит целое число x_0 (-1000000 ≤ x_0 ≤ 1000000), начальную x-координату шарика.
Выходные данные
Выведите одно целое число x_T, конечную x-координату шарика.
Рисунок 1: Пример входных данных 1 Рисунок 2: Пример входных данных 2