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.PrintStream;
import java.io.BufferedInputStream;
import java.util.concurrent.Callable;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Comparator;
import java.util.Collections;

/**
 * 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;
        BufferedInputStream in = new BufferedInputStream(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, BufferedInputStream _in, PrintWriter out) {
            InputReader in = new InputReader(_in);

            long startTime = System.currentTimeMillis();

            int nt = 1;//in.nextInt();

            Task t = new Task(1);
            t.readInput(in);
            t.call();
            t.writeOutput(out);


            in.close();
            System.err.println("Time: " + (System.currentTimeMillis() - startTime) + " miliseconds");
        }

    }

    static enum EndPointChecker {
        NO_ENDPOINT,
        CLOSED_ENDPOINT,
        OPEN_ENDPOINT,;
    }

    static class Polygon {
        public ArrayList<Point> lp = new ArrayList<>();

        int next(int i) {
            return i == lp.size() - 1 ? 0 : i + 1;
        }

        int prev(int i) {
            return i == 0 ? lp.size() - 1 : i - 1;
        }


        public String toString() {
            return "[" + lp + "]";
        }

        boolean orientation() {
            int i = 0;
            Point mn = lp.get(0);

            for (int j = 1; j < lp.size(); ++j)
                if (lp.get(j).compareTo(mn) < 0) {
                    mn = lp.get(j);
                    i = j;
                }
            return Point.ccw(lp.get(prev(i)), lp.get(next(i)), lp.get(i)) > 0;
        }

        public boolean onIncone(int i, Point b) {
            Point a = lp.get(i);
            Point a0 = lp.get(prev(i));
            Point a1 = lp.get(next(i));

            Line l1 = Line.makeLine(a, a0, true);
            if (l1.onLine(b) && b.opSub(a).opMul(l1.ab) >= 0) return true;

            l1 = Line.makeLine(a, a1, true);
            if (l1.onLine(b) && b.opSub(a).opMul(l1.ab) >= 0) return true;


            if (Point.leftOn(a, a1, a0)) {
                return Point.left(a, b, a0) && Point.left(b, a, a1);
            }

            return !(Point.leftOn(a, b, a1) && Point.leftOn(b, a, a0));
        }

        public static boolean stabSimplePolygon(final Line line, final Polygon poly, ArrayList<LineD> ret) {
            class CrossInfo {
                int v;
                //type: 0 normal cross
                //type: 1 cross at vertex
                int type;
                PointD crossPoint;

            }

            ArrayList<CrossInfo> lc = new ArrayList<CrossInfo>();
            int n = poly.lp.size();
            for (int i = 0; i < n; ++i) {
                if (Line.onLine(line, poly.lp.get(i))) {
                    CrossInfo crossInfo = new CrossInfo();
                    crossInfo.v = i;
                    crossInfo.type = 1;
                    crossInfo.crossPoint = new PointD(poly.lp.get(i));

                    lc.add(crossInfo);

                } else {
                    Line seg = new Line(poly.lp.get(i), poly.lp.get(poly.next(i)), true);
                    PointD re = new PointD(0, 0);
                    if (Line.intersectLines(EndPointChecker.NO_ENDPOINT, EndPointChecker.NO_ENDPOINT, EndPointChecker.CLOSED_ENDPOINT, EndPointChecker.OPEN_ENDPOINT, line, seg, re)) {
                        CrossInfo crossInfo = new CrossInfo();
                        crossInfo.v = i;
                        crossInfo.type = 0;
                        crossInfo.crossPoint = re;
                        lc.add(crossInfo);
                    }
                }
            }
            ret.clear();

            if (lc.size() == 1) {
                ret.add(new LineD(lc.get(0).crossPoint, lc.get(0).crossPoint, true));
            } else if (lc.size() > 1) {
                final LineD vect = new LineD(line);
                Comparator<CrossInfo> cmp = new Comparator<CrossInfo>() {

                    public int compare(CrossInfo o1, CrossInfo o2) {
                        PointD lhs = o1.crossPoint;
                        PointD rhs = o2.crossPoint;
                        return Double.valueOf(Point._opSub(lhs, vect.a).opMul(vect.ab)).compareTo(Point._opSub(rhs, vect.a).opMul(vect.ab));
                    }
                };
                Collections.sort(lc, cmp);
                boolean lastIn = false;
                int x = 0;
                PointD begin = null;
                while (x < lc.size()) {
                    CrossInfo infox = lc.get(x);
                    x++;
                    if (lastIn == false) {
                        if (x >= lc.size()) {
                            ret.add(new LineD(infox.crossPoint, infox.crossPoint, true));
                            break;
                        }

                        if (infox.type == 0) {
                            lastIn = true;
                            begin = infox.crossPoint;
                            continue;
                        } else if (infox.type == 1) {
                            Point pv = new Point(poly.lp.get(infox.v));
                            pv.x += line.ab.x;
                            pv.y += line.ab.y;
                            if (poly.onIncone(infox.v, pv)) {
                                lastIn = true;
                                begin = infox.crossPoint;
                                continue;
                            } else {
                                ret.add(new LineD(infox.crossPoint, infox.crossPoint, true));
                            }
                            continue;
                        }
                    } else {
                        if (x >= lc.size()) {
                            ret.add(new LineD(begin, infox.crossPoint, true));
                            continue;
                        }

                        if (infox.type == 0) {
                            lastIn = false;
                            ret.add(new LineD(begin, infox.crossPoint, true));
                            continue;
                        } else {

                            Point pv = new Point(poly.lp.get(infox.v));
                            pv.x += line.ab.x;
                            pv.y += line.ab.y;
                            if (poly.onIncone(infox.v, pv)) {
                                continue;
                            }

                            lastIn = false;
                            ret.add(new LineD(begin, infox.crossPoint, true));
                            continue;
                        }
                    }

                }


            }

            return ret.size() > 0;
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(BufferedInputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

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

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

        public void close() {
            try {
                if (reader != null)
                    reader.close();
            } catch (Exception ex) {
                throw new RuntimeException(ex);
            }
        }

    }

    static class PointD implements Comparable<PointD> {
        public double x;
        public double y;

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

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

        public PointD(PointD o) {
            this.x = o.x;
            this.y = o.y;
        }

        public PointD(Point o) {
            this.x = o.x;
            this.y = o.y;
        }


        public int compareTo(PointD o) {
            int t = Double.valueOf(y).compareTo(o.y);
            if (t != 0)
                return t;


            return Double.valueOf(x).compareTo(o.x);
        }

        public double abs() {
            return (x * x) + (y * y);
        }

        public double norm() {
            return Math.sqrt(abs());
        }

        public double opMul(PointD b) {
            return Point._opMul(this, b);
        }


        public String toString() {
            return "PointD{" +
                    +x +
                    ", " + y +
                    '}';
        }

    }

    static class LineD {
        PointD a;
        PointD ab;

        LineD(PointD a, PointD b, boolean twoPoints) {
            this.a = new PointD(a);
            if (twoPoints) {
                this.ab = Point._opSub(b, a);
            } else {
                this.ab = new PointD(b);
            }
        }

        LineD(double xa, double ya, double xb, double yb) {
            this.a = new PointD(xa, ya);

            this.ab = new PointD((xb - xa), (yb - ya));
        }

        LineD(Line l) {
            this.a = new PointD(l.a);
            this.ab = new PointD(l.ab);
        }

        PointD b() {
            return Point._opPlus(a, ab);
        }


        public String toString() {
            return "LineD{" +
                    a +
                    " " + b() +
                    '}';
        }

    }

    static class Point implements Comparable<Point> {
        public long x;
        public long y;

        public Point(Point o) {
            this.x = o.x;
            this.y = o.y;

        }

        public Point(long x, long y) {
            super();

            this.x = x;
            this.y = y;
        }

        public boolean isZeroPoint() {
            return x == 0 && y == 0;
        }


        public int compareTo(Point o) {
            int t = Long.valueOf(y).compareTo(o.y);
            if (t != 0)
                return t;


            return Long.valueOf(x).compareTo(o.x);
        }

        public long opMul(Point b) {
            return Point._opMul(this, b);
        }

        public long opPow(Point b) {
            return Point._opPow(this, b);
        }

        public Point opSub(Point b) {
            return Point._opSub(this, b);
        }

        public static long _opMul(Point lhs, Point rhs) {

            return ((lhs.x * rhs.x) + (lhs.y * rhs.y));
        }

        public static double _opMul(PointD lhs, PointD rhs) {

            return ((lhs.x * rhs.x) + (lhs.y * rhs.y));
        }

        public static long _opPow(Point lhs, Point rhs) {
            return ((lhs.x * rhs.y) - (lhs.y * rhs.x));
        }

        public static Point _opSub(Point lhs, Point rhs) {
            return new Point((lhs.x - rhs.x), (lhs.y - rhs.y));
        }

        public static PointD _opSub(PointD lhs, PointD rhs) {
            return new PointD((lhs.x - rhs.x), (lhs.y - rhs.y));
        }

        public static Point _opPlus(Point lhs, Point rhs) {
            return new Point((lhs.x + rhs.x), (lhs.y + rhs.y));
        }

        public static PointD _opPlus(PointD lhs, PointD rhs) {
            return new PointD((lhs.x + rhs.x), (lhs.y + rhs.y));
        }

        public static long ccw(Point lhs, Point rhs) {
            return _opPow(rhs, lhs);
        }

        public static long ccw(Point lhs, Point rhs, Point origin) {

            return ccw(new Point((lhs.x - origin.x), (lhs.y - origin.y)), new Point((rhs.x - origin.x), (rhs.y - origin.y)));
        }

        public static boolean left(Point a, Point b, Point c) {
            return Point.ccw(c, b, a) > 0;
        }

        public static boolean leftOn(Point a, Point b, Point c) {
            return Point.ccw(c, b, a) >= 0;
        }


        public String toString() {
            return x + " " + y;
        }

    }

    static class Line {
        Point a;
        Point ab;

        Line(Point a, Point b, boolean twoPoints) {
            this.a = new Point(a);
            if (twoPoints) {
                this.ab = Point._opSub(b, a);
            } else {
                this.ab = new Point(b);
            }
        }

        Line(long xa, long ya, long xb, long yb) {
            this.a = new Point(xa, ya);

            this.ab = new Point((xb - xa), (yb - ya));
        }

        Point b() {
            return Point._opPlus(a, ab);
        }

        boolean onLine(Point point) {
            if (this.ab.isZeroPoint()) return a.compareTo(point) == 0;

            return Point._opPow(Point._opSub(point, this.a), this.ab) == 0;
        }


        public String toString() {
            return "Line{" +
                    "(" + a +
                    ") (" + b() +
                    ")}";
        }

        public static boolean onLine(Line l, Point p) {
            return l.onLine(p);
        }

        public static Line makeLine(Point p1, Point p2, boolean twoPoints) {
            return new Line(p1, p2, twoPoints);
        }

        private static boolean endpointCheck(EndPointChecker checker, long a, long b) {
            switch (checker) {
                case NO_ENDPOINT:
                    return true;
                case CLOSED_ENDPOINT:
                    return a <= b;
                case OPEN_ENDPOINT:
                    return a < b;
                default:
                    throw new RuntimeException();
            }
        }

        public static boolean intersectLines(EndPointChecker LA,
                                             EndPointChecker LB,
                                             EndPointChecker RA,
                                             EndPointChecker RB,
                                             Line lhs,
                                             Line rhs,
                                             PointD ret) {
            if (lhs.ab.isZeroPoint() || rhs.ab.isZeroPoint()) {
                System.err.println(lhs);
                System.err.println(rhs);
                throw new RuntimeException();
            }

            long s = lhs.ab.opPow(rhs.ab);
            if (s == 0) return false;
            //        auto ls = (rhs.a - lhs.a) ^ rhs.ab;
            //        auto rs = (rhs.a - lhs.a) ^ lhs.ab;
            //        if (s < 0) s = -s, ls = -ls, rs = -rs;
            long ls = rhs.a.opSub(lhs.a).opPow(rhs.ab);
            long rs = rhs.a.opSub(lhs.a).opPow(lhs.ab);
            if (s < 0) {
                s = (-s);
                ls = (-ls);
                rs = (-rs);
            }

            boolean intersect = endpointCheck(LA, 0l, ls) && endpointCheck(LB, ls, s) &&
                    endpointCheck(RA, 0l, rs) && endpointCheck(RB, rs, s);

            if (intersect) {
                ret.x = lhs.a.x;
                ret.y = lhs.a.y;
                double temp = (double) ls / s;
                ret.x += temp * lhs.ab.x;
                ret.y += temp * lhs.ab.y;
            }
            return intersect;
        }

    }

    static class Task implements Callable<Task> {
        int n;
        int m;
        Polygon poly = new Polygon();
        ArrayList<Line> ll = new ArrayList<>();
        StringBuilder re = new StringBuilder();
        int testNumber;

        long StringToLong(String str) {
            long ret = 0;

            if (str.indexOf('.') < 0) {
                str = str + ".00";
            }

            int pos = str.indexOf('.');
            int add = 3 - (str.length() - pos);
            for (int i = 0; i < add; ++i) str += "0";

            return Long.valueOf(str.substring(0, pos) + str.substring(pos + 1));
        }

        public void readInput(InputReader in) {
    /* read input here */
            n = in.nextInt();
            m = in.nextInt();
            for (int i = 0; i < n; ++i) {
                poly.lp.add(new Point(StringToLong(in.next()), StringToLong(in.next())));
            }
            for (int i = 0; i < m; ++i) {
                ll.add(new Line(StringToLong(in.next()), StringToLong(in.next()), StringToLong(in.next()), StringToLong(in.next())));
            }
        }

        public Task call() {
    /* process main algorithm here */
            if (!poly.orientation()) {
                Collections.reverse(poly.lp);
            }

            for (int i = 0; i < m; ++i) {
                ArrayList<LineD> lre = new ArrayList<>();
                Polygon.stabSimplePolygon(ll.get(i), poly, lre);
                double sum = 0;
                for (LineD li : lre) {
                    sum += li.ab.norm();
                }
                re.append(String.format("%.15f\n", sum / 100));
            }

            System.err.println("Test case: " + testNumber + " done!");
            return this;
        }

        public void writeOutput(PrintWriter out) {
            out.println(re);
        }

        Task(int testNumber) {
            this.testNumber = testNumber;
        }

    }
}