Камера спостереження#1832

Камера спостереження

2 секунди

256 мегабайтів

Дуже складна

У точці $S$ знаходиться камера. Її мета — спостерігати за об'єктом, який рухається на велосипеді з точки $A$ до точки $B$ по прямій. Камера може "бачити" об'єкт миттєво по прямій траєкторії, але її лінія огляду не може проходити через внутрішню частину жодної будівлі. На місцевості розташовано $N$ хмарочосів у вигляді паралелепіпедів, які є перешкодами. Камера прагне побачити об'єкт якнайшвидше. Ваше завдання — визначити координати об'єкта в момент, коли він вперше стане видимим для камери.

Вхідні дані

У першому рядку — координати точки $S$ : $s x$ , $sy$ , $sz$ ( $sz \geq 0$ sz \geq 0), розділені пробілами.

У другому рядку — координати точок $A$ та $B$ : $a x$ , $a y$ , $b x$ , $b y$ , розділені пробілами. Протягом усього руху $z$ -координата об'єкта завжди дорівнює нулю.

Далі йдуть $N$ ( $0 \leq N \leq 1000$ 0 \leq N \leq 1000) рядків, у кожному з яких записано $l x$ , $l y$ , $r x$ , $r y$ , $h$ ( $l x < r x$ lx < rx, $l y < r y$ ly < ry, $h > 0$ h > 0) — координати двох протилежних кутів основи кожної будівлі та її висота. Сторони хмарочосів паралельні осям декартової системи координат.

Усі координати та висоти — цілі числа за модулем не більші за $100$ . Гарантується, що жодна пара будівель не має спільних точок, відрізок $A B$ не перетинає жодної з будівель, а точка $S$ не знаходиться всередині жодної будівлі.

Вихідні дані

Якщо камері неможливо спостерігати за об'єктом (лінія огляду завжди перекрита), виведіть Impossible. Інакше виведіть координати об'єкта в момент, коли він вперше стане видимим, з точністю до $1 0^{- 7}$ 10^{-7}.

Приклади

Приклад 1