eolymp
bolt
Try our new interface for solving problems
Problems

Пересечение отрезков

Пересечение отрезков

Time limit 1 second
Memory limit 64 MiB

Даны два отрезка: AB и CD. Определите, какое множество точек является пересечением этих отрезков.

Input data

Программа получает на вход восемь целых чисел, по абсолютной величине не превосходящих 10^4 - координаты точек A, B, C, D. Точки могут совпадать (в том числе могут совпадать и концы одного отрезка).

Output data

Если указанные отрезки не пересекаются, то выведите строку Empty. Если отрезки пересекаются в одной точке, то выведите два числа - координаты точки пересечения. Если пересечением является отрезок, то выведите четыре числа - координаты двух концов отрезка в лексикографическом порядке (то есть сначала нужно вывести ту точку, у которой меньше координата x, а если у них равны координаты x то ту, у которой меньше координата y). Все числа следует выводить с точностью не менее 6 знаков после запятой.

Examples

Input example #1
0 0
9 9
9 5
0 5
Output example #1
5.0000000000 5.0000000000