Given simple (without self-intersections) $n$-gon. It is not necessary convex. Also you are given $m$ lines. For each line find the length of common part of the line and the $n$-gon.

The boundary of $n$-gon belongs to polygon. It is possible that $n$-gon contains 180-degree angles.

Оролт

The first line contains integers $n$ and $m$ ($3 ≤ n ≤ 1000;1 ≤ m ≤ 100$). The following $n$ lines contain coordinates of polygon vertices (in clockwise or counterclockwise direction). All vertices are distinct.

The following $m$ lines contain line descriptions. Each of them contains two distict points of a line by their coordinates.

All given in the input coordinates are real numbers, given with at most two digits after decimal point. They do not exceed $10^{5}$ by absolute values.

Гаралт

Print $m$ lines, the $i$-th line should contain the length of common part of the given $n$-gon and the $i$-th line. The answer will be considered correct if the absolute or relative error doesn't exceed $10^{ - 6}$.