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

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

  static class TaskF {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
      int n = in.nextInt();
      int m = in.nextInt();
      Point[] points = new Point[n + 2];
      for (int i = 1; i <= n; i++) {
        long x = (long) (in.nextDouble() * 100.0);
        long y = (long) (in.nextDouble() * 100.0);
        points[i] = new Point(x, y);
      }
      points[0] = points[n];
      points[n + 1] = points[1];
      for (int i = 0; i < m; i++) {
        long x1 = (long) (in.nextDouble() * 100.0);
        long y1 = (long) (in.nextDouble() * 100.0);
        long x2 = (long) (in.nextDouble() * 100.0);
        long y2 = (long) (in.nextDouble() * 100.0);
        out.printf("%.12f\n", solve(points, new Point(x1, y1), new Point(x2, y2)) / 100.0);
      }
    }

    private double solve(Point[] points, Point a, Point b) {
      int n = points.length - 2;
      List<Pair<DoublePoint, Integer>> events = new ArrayList<>(n << 1);

      for (int i = 1; i <= n; i++) {
        int fd1 = Long.signum(Geos.crossProd(points[i - 1], b, a));
        int fd2 = Long.signum(Geos.crossProd(points[i], b, a));
        int fd3 = Long.signum(Geos.crossProd(points[i + 1], b, a));
        if (fd2 * fd3 < 0)
          events.add(Pair.of(Geos.intersection(points[i], points[i + 1], a, b), 0));
        else if (fd2 == 0 && fd1 != fd3) events.add(Pair.of(new DoublePoint(points[i]), fd1 + fd3));
      }
      Collections.sort(events);
      double sumX = 0, sumY = 0;
      boolean ok = false;
      DoublePoint prev = null;
      int current = 0;
      for (Pair<DoublePoint, Integer> event : events) {
        if (current != 0 || ok) {
          sumX += event.first.x - prev.x;
          sumY += event.first.y - prev.y;
        }
        if (current == 0) {
          if (event.second == 0) ok = !ok;
          else current = event.second;
        } else {
          if (current != event.second) ok = !ok;
          current = 0;
        }
        prev = event.first;
      }

      return Math.hypot(sumX, sumY);
    }

  }

  static class OutputWriter {
    private final PrintWriter writer;

    private OutputWriter(Writer writer, boolean autoFlush) {
      this.writer = new PrintWriter(new BufferedWriter(writer, 32767), autoFlush);
    }

    public OutputWriter(Writer writer) {
      this(writer, true);
    }

    public OutputWriter(OutputStream outputStream) {
      this(new OutputStreamWriter(outputStream), false);
    }

    public OutputWriter printf(String format, Object... objects) {
      writer.printf(format, objects);
      return this;
    }

    public void close() {
      writer.close();
    }

  }

  static class InputReader {
    public final BufferedReader reader;
    public StringTokenizer tokenizer = null;

    public InputReader(Reader reader) {
      this.reader = new BufferedReader(reader, 32767);
    }

    public InputReader(InputStream inputStream) {
      this(new InputStreamReader(inputStream));
    }

    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 double nextDouble() {
      return Double.parseDouble(next());
    }

  }

  static class DoublePoint implements Comparable<DoublePoint> {
    private static final double EPS = 1e-8;
    public double x;
    public double y;

    private static int doubleSignum(double x) {
      return x < -EPS ? -1 : x > EPS ? 1 : 0;
    }

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

    public DoublePoint(Point p) {
      this.x = p.x;
      this.y = p.y;
    }


    public int compareTo(DoublePoint other) {
      int fd = doubleSignum(x - other.x);
      if (fd != 0) return fd;
      else return doubleSignum(y - other.y);
    }


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

  }

  static class Pair<F extends Comparable<F>, S extends Comparable<S>> implements Comparable<Pair<F, S>> {
    public F first;
    public S second;

    public Pair(F first, S second) {
      this.first = first;
      this.second = second;
    }

    public static <F extends Comparable<F>, S extends Comparable<S>> Pair<F, S> of(
        F first, S second) {
      return new Pair<>(first, second);
    }


    public int compareTo(Pair<F, S> other) {
      int fd = this.first.compareTo(other.first);
      if (fd != 0) return fd;
      else return this.second.compareTo(other.second);
    }


    public String toString() {
      return "Pair{" + first + ", " + second + "}";
    }


    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;

      Pair<?, ?> pair = (Pair<?, ?>) o;

      if (first != null ? !first.equals(pair.first) : pair.first != null) return false;
      return !(second != null ? !second.equals(pair.second) : pair.second != null);

    }


    public int hashCode() {
      return Objects.hash(first, second);
    }

  }

  static class Point {
    public long x;
    public long y;

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

    public Point subtract(Point p) {
      return new Point(x - p.x, y - p.y);
    }

    public long crossProduct(Point p) {
      return x * p.y - y * p.x;
    }


    public String toString() {
      return String.format("(%d, %d @ %.4f)", x, y, Math.atan2(y, x));
    }

  }

  static class Geos {
    private Geos() {
    }

    public static long crossProd(Point a, Point b, Point o) {
      return a.subtract(o).crossProduct(b.subtract(o));
    }

    public static DoublePoint intersection(Point a, Point b, Point c, Point d) {
      double u = b.subtract(a).crossProduct(c.subtract(a));
      double v = a.subtract(b).crossProduct(d.subtract(b));
      return new DoublePoint((c.x * v + d.x * u) / (u + v), (c.y * v + d.y * u) / (u + v));
    }

  }
}