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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

// Educational Codeforces Round 1
// Cut Length
public class Problem_598_F {
    

    public static void main(String[] args)
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        PrintWriter out = new PrintWriter(outputStream);
        Problem_598_F solver = new Problem_598_F();
        solver.solve(1, new InputStreamReader(inputStream), out);
        out.close();
    }
    
    static class Point implements Comparable<Point> {
      double first;

      double second;

      Point(double f, double s)
      {
        first = f;
        second = s;
      }

      public int compareTo(Point o)
      {
        int r = Double.compare(first, o.first);

        if(r == 0)
          r = Double.compare(second, o.second);

        return r;
      }
    }
    
    static class Pair implements Comparable<Pair> {
      double first;

      double second;
      
      int ok;

      Pair(int o, double f, double s)
      {
        ok = o;
        first = f;
        second = s;
      }
      
      Pair(int o)
      {
        ok = o;
      }

      public int compareTo(Pair o)
      {
        int r = Double.compare(first, o.first);

        if(r == 0)
          r = Double.compare(second, o.second);

        return r;
      }
    }
    
    static class Line {
      double x1, y1, x2, y2;
    }
    
    Point[] poly;
    private int n;
    private int m;

    static final double EPS = 1e-10;
    
    boolean isZero(double x)
    {
        return Math.abs(x) <= EPS;
    }

    Pair cross(Line line, Point p1, Point p2)
    {
        double dx = line.x2-line.x1;
        double dy = line.y2-line.y1;
        double dt = (dx*(p1.second-line.y1)-dy*(p1.first-line.x1))*(dx*(p2.second-line.y1)-dy*(p2.first-line.x1));
        if(dt > 0 || isZero(dt))
            return new Pair(0);
        if(isZero(dx) && isZero(p2.first-p1.first))
            return new Pair(0);
        if(isZero(dx))
        {
            double a = (p1.second-p2.second)/(p1.first-p2.first);
            double b = p1.second-a*p1.first;
            return new Pair(1, line.x1, a*line.x1+b);
        }
        if(isZero(p2.first-p1.first))
        {
            double a = (line.y1-line.y2)/(line.x1-line.x2);
            double b = line.y1-a*line.x1;
            return new Pair(1, p1.first, a*p1.first+b);
        }
        double a1 = (p1.second-p2.second)/(p1.first-p2.first);
        double b1 = p1.second-a1  *p1.first;
        double a2 = (line.y1-line.y2)/(line.x1-line.x2);
        double b2 = line.y1-a2*line.x1;
        double x = (b2-b1)/(a1-a2);
        double y = a1*x+b1;
        return new Pair(1, x, y);
    }

    double len(Pair p1, Pair p2)
    {
        double dx = p2.first-p1.first;
        double dy = p2.second-p1.second;
        return Math.sqrt(dx*dx+dy*dy);
    }

    boolean onLine(Line line, Point p)
    {
        if(isZero(line.x2-line.x1))
            return isZero(line.x1-p.first);
        double a = (line.y1-line.y2)/(line.x1-line.x2);
        double b = line.y1-a*line.x1;
        return isZero(a*p.first+b-p.second);
    }
    
    int diff(int p1, int p2, Line line)
    {
        Point pa = new Point(poly[(p1-1+n)%n].first-line.x1, poly[(p1-1+n)%n].second-line.y1);
        Point pb = new Point(poly[(p1+1)%n].first-line.x1, poly[(p1+1)%n].second-line.y1);
        double dx = line.x2-line.x1;
        double dy = line.y2-line.y1;
        if(p1 == p2)
        {
            double dt = (dx*pa.second-dy*pa.first)*(dx*pb.second-dy*pb.first);
            if(dt < 0 && !isZero(dt))
                return 1;
            return 0;
        }
        else
        {
            Point pc = new Point(poly[(p2-1+n)%n].first-line.x1, poly[(p2-1+n)%n].second-line.y1);
            Point pd = new Point(poly[(p2+1)%n].first-line.x1, poly[(p2+1)%n].second-line.y1);
            double d1 = (dx*pa.second-dy*pa.first)*(dx*pc.second-dy*pc.first);
            if(d1 < 0 && !isZero(d1)) return 1;
            if(d1 > 0 && !isZero(d1)) return 0;
            d1 = (dx*pa.second-dy*pa.first)*(dx*pd.second-dy*pd.first);
            if(d1 < 0 && !isZero(d1)) return 1;
            if(d1 > 0 && !isZero(d1)) return 0;
            d1 = (dx*pb.second-dy*pb.first)*(dx*pd.second-dy*pd.first);
            if(d1 < 0 && !isZero(d1)) return 1;
            if(d1 > 0 && !isZero(d1)) return 0;
            d1 = (dx*pb.second-dy*pb.first)*(dx*pc.second-dy*pc.first);
            if(d1 < 0 && !isZero(d1)) return 1;
            return 0;
        }
    }
    double calc(Line line)
    {
        ArrayList<Pair> p = new ArrayList<>();
        for(int i = 0; i < n; ++i)
        {
            Pair tp = cross(line, poly[i], poly[(i+1)%n]);
            if(tp.ok == 0) continue;
            tp.ok = -1;
            p.add(tp);
        }
        for(int i = 0; i < n; ++i)
        {
            if(onLine(line, poly[i]))
                p.add(new Pair(i, poly[i].first, poly[i].second));
        }
        Collections.sort(p);
        double w = 0;
        int pts = 0;
        for(int i = 0; i < (int)(p.size())-1; ++i)
        {
            if(p.get(i).ok == -1)
            {
                ++pts;
                if(pts%2 == 1)
                    w += len(p.get(i), p.get(i+1));
            }
            else
            {
                int b = i, e = i;
                while(e+1 < p.size() && p.get(e+1).ok == (p.get(e).ok+1)%n) ++e;
                if(b == e)
                    while(e+1 < p.size() && p.get(e+1).ok == (p.get(e).ok-1+n)%n)
                        ++e;
                w += len(p.get(b), p.get(e));
                pts += diff(p.get(b).ok, p.get(e).ok, line);
                i = e;
                if(pts%2 == 1 && i+1 < p.size())
                    w += len(p.get(i), p.get(i+1));
            }
        }
        return w;
    }
    public void solve(int test, Reader input, PrintWriter out)
    {
        MyScanner in = new MyScanner(input);
        
        n = in.nextInt();
        m = in.nextInt();
        
        poly = new Point[n];
        for(int i = 0; i < n; i++) {
          poly[i] = new Point(in.nextDouble(), in.nextDouble());
        }
        
        Line line = new Line();
        
        for(int i = 0; i < m; i++) {
          line.x1 = in.nextDouble();
          line.y1 = in.nextDouble();
          line.x2 = in.nextDouble();
          line.y2 = in.nextDouble();
          
          out.printf("%.10f\n", calc(line));
        }
    }

    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner(Reader reader) {
            br = new BufferedReader(reader);
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
    //--------------------------------------------------------

}