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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using V = vector<T>;
int gcdex(int a, int b, int &x, int &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  int x1, y1;
  int g = gcdex(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return g;
}
inline int ADD_MOD(int a, int b) { return (a + b) % 1000000007; }
inline int MUL_MOD(int a, int b) { return (int64_t(a) * b) % 1000000007; }
inline int SUB_MOD(int a, int b) { return a >= b ? a - b : a + 1000000007 - b; }
int DIV_MOD(int a, int b) {
  int x, y;
  gcdex(b, 1000000007, x, y);
  int b1 = (x % 1000000007 + 1000000007) % 1000000007;
  return MUL_MOD(a, b1);
}
const long double EPS = 1. / 1e9;
inline bool EPS_EQUAL(long double a, long double b) {
  return abs(a - b) <= EPS;
}
inline bool EPS_LESS(long double a, long double b) { return b - a > EPS; }
inline bool EPS_GREATER(long double a, long double b) { return a - b > EPS; }
const int INF = 1e9;
struct Point2d {
  long double x = 0, y = 0;
  Point2d() {}
  Point2d(long double x, long double y) : x(x), y(y) {}
  long double len() { return sqrt(x * x + y * y); }
  long double dist(Point2d &p) {
    Point2d dif(p.x - x, p.y - y);
    return dif.len();
  }
  Point2d to_vec(Point2d &a) { return Point2d(x - a.x, y - a.y); }
  Point2d norm() {
    long double l = len();
    return Point2d(x / l, y / l);
  }
  Point2d operator+(Point2d const &a) const {
    return Point2d(x + a.x, y + a.y);
  }
  Point2d operator/(long double a) const { return Point2d(x / a, y / a); }
};
struct Line2d {
  long double a, b, c;
  Line2d() {}
  Line2d(Point2d &p1, Point2d &p2) {
    a = p1.y - p2.y;
    b = p2.x - p1.x;
    c = -(a * p1.x + b * p1.y);
    norm();
  }
  void norm() {
    long double d = sqrt(a * a + b * b);
    if (abs(d) > EPS) {
      a /= d;
      b /= d;
      c /= d;
    }
  }
  long double dist(Point2d p) { return abs(p.x * a + p.y * b + c); }
};
struct Intersection {
  Point2d p;
  bool in;
  Intersection() {}
  Intersection(Point2d p, bool in) : p(p), in(in) {}
};
bool is_cw(V<Point2d> &points) {
  long double res = 0;
  int n = points.size();
  for (int i = 0; i < n; ++i) {
    Point2d &p1 = points[i];
    Point2d &p2 = points[(i + 1) % n];
    res += (p2.x - p1.x) * (p2.y + p1.y);
  }
  return res > 0;
}
long double det(long double a, long double b, long double c, long double d) {
  return a * d - b * c;
}
long double betw(long double l, long double r, long double x) {
  return x + EPS >= min(l, r) && x <= max(l, r) + EPS;
}
bool sort_inters(Intersection const &a, Intersection const &b) {
  if (EPS_EQUAL(a.p.x, b.p.x)) {
    return EPS_LESS(a.p.y, b.p.y);
  }
  return EPS_LESS(a.p.x, b.p.x);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.precision(15);
  int n, m;
  cin >> n >> m;
  V<Point2d> points(n);
  for (int i = 0; i < n; ++i) {
    cin >> points[i].x >> points[i].y;
  }
  if (is_cw(points)) {
    reverse(points.begin(), points.end());
  }
  V<Line2d> polyLines(n);
  for (int i = 0; i < n; ++i) {
    polyLines[i] = Line2d(points[i], points[(i + 1) % n]);
  }
  for (int i = 0; i < m; ++i) {
    Point2d p1, p2;
    cin >> p1.x >> p1.y >> p2.x >> p2.y;
    Line2d line(p1, p2);
    V<Intersection> inters;
    for (int j = 0; j < n; ++j) {
      Line2d &edge = polyLines[j];
      Point2d &edgeP1 = points[j];
      Point2d &edgeP2 = points[(j + 1) % n];
      long double d = det(line.a, line.b, edge.a, edge.b);
      if (abs(d) > EPS) {
        long double x = -det(line.c, line.b, edge.c, edge.b) / d;
        long double y = -det(line.a, line.c, edge.a, edge.c) / d;
        if (betw(edgeP1.x, edgeP2.x, x) && betw(edgeP1.y, edgeP2.y, y)) {
          bool in = d < 0;
          if (inters.empty() || inters.back().in != in) {
            inters.push_back({{x, y}, in});
          }
        }
      } else {
        if (line.dist(edgeP1) < EPS && edge.dist(p1) < EPS) {
          Point2d lineVec = p1.to_vec(p2).norm();
          Point2d edgeVec = edgeP1.to_vec(edgeP2).norm();
          if (EPS_EQUAL(lineVec.x, edgeVec.x) &&
              EPS_EQUAL(lineVec.y, edgeVec.y)) {
            if (inters.empty() || !inters.back().in) {
              inters.push_back({edgeP1, true});
            }
            inters.push_back({edgeP2, false});
          } else {
            if (inters.empty() || inters.back().in) {
              inters.push_back({edgeP1, false});
            }
            inters.push_back({edgeP2, true});
          }
        }
      }
    }
    if (!inters.empty() && inters.front().in == inters.back().in) {
      inters.pop_back();
    }
    long double dist = 0;
    if (!inters.empty()) {
      sort(inters.begin(), inters.end(), sort_inters);
      for (int j = 0; j < inters.size(); j += 2) {
        Point2d pIn = inters[j].p;
        Point2d pOut = inters[j + 1].p;
        dist += pIn.dist(pOut);
      }
    }
    cout << dist << endl;
  }
  return 0;
}