F. Длина разреза
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан простой (без самопересечений) n-угольник. Заданный многоугольник не обязательно выпуклый. Также на плоскости задано m прямых. Для каждой прямой выведите длину общей части многоугольника и прямой.

Граница многоугольника является его частью. Многоугольник, возможно, содержит развернутые углы при своих вершинах.

Входные данные

В первой строке заданы числа n и m (3 ≤ n ≤ 1000;1 ≤ m ≤ 100). Далее в n строках записаны координаты вершин многоугольника в порядке некоторого обхода. Никакие две вершины не совпадают.

Потом следует m строк, каждая из которых содержит координаты двух различных точек, задающих прямую.

Все координаты во входных данных — вещественные числа, заданные не более чем с двумя знаками после десятичной точки. По модулю числа не превосходят 105.

Выходные данные

Выведите m строк. Каждая строка должна содержать длину общей части многоугольника и соответствующей прямой. Допускается абсолютная или относительная погрешность не более 10 - 6.

Примеры
Входные данные
4 3
0 0
1 0
1 1
0 1
0 0 1 1
0 0 0 1
0 0 1 -1
Выходные данные
1.41421356237309514547
1.00000000000000000000
0.00000000000000000000