Дождь
Дождь
Капля дождя падает вертикально вниз с большой высоты на землю. На пути у капли могут встретиться препятствия, которые изменяют ее путь к земле.
Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.
Напишите программу, которая по координате X0 точки появления капли над землей вычисляет координату X точки соприкосновения капли с землей (Y = 0).
Входные данные
Во входном файле в первой строке содержатся два целых числа через пробел – координата X0 точки появления капли (0 < X0 < 10000) и количество отрезков-препятствий N (0 ≤ N ≤ 100). Далее следует N строк, каждая из которых содержит четыре разделенные пробелами числа x1 , y1,x2, y2 – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от 0 до 10000, x1 < x2, y1 ≠ y2). Отрезки не пересекаются и не соприкасаются.
Выходные данные
В выходной файл вывести одно целое число – координату X точки соприкосновения капли с землей.
Пример
30 4 25 35 40 30 1 32 20 30 33 22 50 29 18 10 33 19
18