Problem: 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.

Input

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 105 by absolute values.

Output

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.

Examples

Input

4 3
0 0
1 0
1 1
0 1
0 0 1 1
0 0 0 1
0 0 1 -1


Output

1.41421356237309514547
1.00000000000000000000
0.00000000000000000000

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskF solver = new TaskF();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskF {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            Point[] p = new Point[n];
            for (int i = 0; i < n; i++) {
                p[i] = nextPoint(in);
            }
            for (int queryId = 0; queryId < m; queryId++) {
                Point p1 = nextPoint(in);
                Point p2 = nextPoint(in);
                PointDouble v = p2.sub(p1).toPointDouble();
                v.normalize();
                List<Event> events = new ArrayList<>();
                int[] nextNonZero = new int[n];
                int[] prevNonZero = new int[n];
                int anyNonZero = -1;
                for (int i = 0; i < n; i++) {
                    Point a = p[(i + n - 1) % n];
                    Point b = p[i];
                    Point c = p[(i + 1) % n];
                    int sa = side(a, p1, p2);
                    int sb = side(b, p1, p2);
                    int sc = side(c, p1, p2);
                    if (sb != 0) {
                        anyNonZero = i;
                    }
                    if (sb * sc < 0) {
                        PointDouble x = intersect(b, c, p1, p2);
                        double tx = dot(x, v);
                        events.add(new Event(tx, -1));
                    } else if (sb == 0) {
                        double tb = dot(b.toPointDouble(), v);
                        if (sa * sc < 0) {
                            events.add(new Event(tb, -1));
                        }
                        if ((sa == 0) ^ (sc == 0)) {
                            events.add(new Event(tb, i));
                        }
                    }
                }
                if (anyNonZero < 0) {
                    throw new AssertionError("area = 0");
                }
                {
                    int s = 0;
                    int i = anyNonZero;
                    for (int j = 0; j < n; j++) {
                        int ns = side(p[i], p1, p2);
                        if (ns == 0) {
                            prevNonZero[i] = s;
                        } else {
                            s = ns;
                        }
                        i = (i + 1) % n;
                    }
                    s = 0;
                    i = anyNonZero;
                    for (int j = 0; j < n; j++) {
                        int ns = side(p[i], p1, p2);
                        if (ns == 0) {
                            nextNonZero[i] = s;
                        } else {
                            s = ns;
                        }
                        i = (i + n - 1) % n;
                    }
                }

                double ans = 0;
                Collections.sort(events);
                boolean open = false;
                double px = 0;
                for (int eid = 0; eid < events.size(); ) {
                    Event e1 = events.get(eid++);
                    if (e1.pointId < 0) {
                        if (!open) {
                            px = e1.x;
                            open = true;
                        } else {
                            ans += e1.x - px;
                            open = false;
                        }
                        continue;
                    }
                    if (eid >= events.size()) {
                        throw new AssertionError();
                    }
                    Event e2 = events.get(eid++);

                    int i = e1.pointId;
                    if (prevNonZero[i] == nextNonZero[i]) {
                        if (!open) {
                            ans += e2.x - e1.x;
                        }
                    } else {
                        if (!open) {
                            px = e1.x;
                            open = true;
                        } else {
                            ans += e2.x - px;
                            open = false;
                        }
                    }
                }
                out.printf("%.15f\n", 1e-2 * ans);
            }
        }

        private int side(Point a, Point p1, Point p2) {
            return Long.signum(cross(a.sub(p1), p2.sub(p1)));
        }

        private PointDouble intersect(Point a, Point b, Point p, Point q) {
            double d1 = cross(p.sub(a), b.sub(a));
            double d2 = cross(q.sub(a), b.sub(a));
            if (d1 == d2) {
                return null;
            }
            double x = (d1 * q.x - d2 * p.x) / (d1 - d2);
            double y = (d1 * q.y - d2 * p.y) / (d1 - d2);
            return new PointDouble(x, y);
        }

        private long cross(Point p1, Point p2) {
            return p1.x * p2.y - p1.y * p2.x;
        }

        private double dot(PointDouble p1, PointDouble p2) {
            return p1.x * p2.x + p1.y * p2.y;
        }

        private Point nextPoint(FastScanner in) {
            long x = nextDoubleToLong(in);
            long y = nextDoubleToLong(in);
            return new Point(x, y);
        }

        private long nextDoubleToLong(FastScanner in) {
            String s = in.next();
            long sign = 1;
            if (s.startsWith("-")) {
                sign = -1;
                s = s.substring(1);
            }
            long x = (long) (Double.parseDouble(s) * 100 + 1e-5);
            return x * sign;
        }

        class Point {
            long x;
            long y;

            Point(long x, long y) {
                this.x = x;
                this.y = y;
            }

            Point sub(Point o) {
                return new Point(x - o.x, y - o.y);
            }

            PointDouble toPointDouble() {
                return new PointDouble(x, y);
            }

        }

        class PointDouble {
            double x;
            double y;

            PointDouble(double x, double y) {
                this.x = x;
                this.y = y;
            }

            void normalize() {
                double len = Math.sqrt(x * x + y * y);
                x /= len;
                y /= len;
            }

        }

        class Event implements Comparable<Event> {
            double x;
            int pointId;

            Event(double x, int pointId) {
                this.x = x;
                this.pointId = pointId;
            }

            public int compareTo(Event o) {
                return Double.compare(x, o.x);
            }

        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}