eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків

Дощ

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Крапля дощу падає вертикально вниз з великої висоти на землю. На шляху у краплі можуть зустрітися перешкоди, які змінюютї її шлях до землі.

Будемо розглядати двомірний варвант (на площині) цієї задачі. Нехай перешкоди – це нахилені відрізки, що не перестинаються, а крапля має точкові розміри. Крапля падає вертикально вниз з точки, розміщеної вище довільної з перешкод. Якщо крапля при падінні дотикається з відрізком-перешкодою, то вона зтікає по відрізку вниз, доки не впаде вертикально вниз з меншого за висотою кінця відрізка.

Напишіть програму, яка за координатою X_0 точки появи краплі над землею обчислює координату X точки дотику краплі з землею (Y  =  0).

Вхідні дані

У вхідному файлі в першому рядку міститься два цілих числа через пропуск – координата X_0 точки появи краплі (0  < X_0  <  10000) та кількість відрізків-перешкод N (0  ≤ N  ≤  100). Далі йде N рядків, кожен з яких містить чотири відокремдених пропусками числа x_1 ,  y_1,x_2,   y_2_ – координати лівого та правого кінців відрізка-перешкоди (всі числа цілі і знаходяться у діапазоні від 0 до 10000, x_{1 } <  x_2, y_{1 } ≠  y_2). Відрізки не перетинаються і не дотикаються.

Вихідні дані

У вихідний файл вивести одне ціле число – координату X точки дотику краплі з землею.

Приклад

Вхідні дані #1
30 4
25 35 40 30
1 32 20 30
33 22 50 29
18 10 33 19
Вихідні дані #1
18