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;
using ld = long double;
using lli = long long;
using vi = vector<lli>;
using graph = vector<vi>;
const double PI = 2 * acos(0.0);
template <class first>
struct Point {
  first x, y;
  Point() : x(0), y(0) {}
  Point(const first& x, const first& y) : x(x), y(y) {}
  void swap(Point& other) {
    using std::swap;
    swap(x, other.x);
    swap(y, other.y);
  }
  template <class F1>
  explicit operator Point<F1>() const {
    return Point<F1>(static_cast<F1>(x), static_cast<F1>(y));
  }
  template <class F1>
  Point& operator=(const Point<F1>& other) {
    x = other.x;
    y = other.y;
    return *this;
  }
  template <class F1>
  Point& operator+=(const Point<F1>& other) {
    x += other.x;
    y += other.y;
    return *this;
  }
  template <class F1>
  Point& operator-=(const Point<F1>& other) {
    x -= other.x;
    y -= other.y;
    return *this;
  }
  template <class F1>
  Point& operator*=(const F1& factor) {
    x *= factor;
    y *= factor;
    return *this;
  }
  template <class F1>
  Point& operator/=(const F1& factor) {
    x /= factor;
    y /= factor;
    return *this;
  }
};
template <class first>
istream& operator>>(istream& is, Point<first>& point) {
  return is >> point.x >> point.y;
}
template <class first>
ostream& operator<<(ostream& os, const Point<first>& point) {
  return os << point.x << ' ' << point.y;
}
template <class first>
inline Point<first> makePoint(const first& x, const first& y) {
  return Point<first>(x, y);
}
template <class first>
void swap(Point<first>& lhs, Point<first>& rhs) {
  lhs.swap(rhs);
}
template <class first>
inline auto operator-(const Point<first>& point)
    -> decltype(makePoint(-point.x, -point.y)) {
  return makePoint(-point.x, -point.y);
}
template <class F1, class F2>
inline auto operator+(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(makePoint(lhs.x + rhs.x, lhs.y + rhs.y)) {
  return makePoint(lhs.x + rhs.x, lhs.y + rhs.y);
}
template <class F1, class F2>
inline auto operator-(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(makePoint(lhs.x - rhs.x, lhs.y - rhs.y)) {
  return makePoint(lhs.x - rhs.x, lhs.y - rhs.y);
}
template <class F1, class F2>
inline auto operator*(const F1& factor, const Point<F2>& rhs)
    -> decltype(makePoint(factor * rhs.x, factor* rhs.y)) {
  return makePoint(factor * rhs.x, factor * rhs.y);
}
template <class F1, class F2>
inline auto operator*(const Point<F1>& lhs, const F2& factor)
    -> decltype(makePoint(lhs.x * factor, lhs.y* factor)) {
  return makePoint(lhs.x * factor, lhs.y * factor);
}
template <class F1, class F2>
inline auto operator/(const Point<F1>& lhs, const F2& factor)
    -> decltype(makePoint(lhs.x / factor, lhs.y / factor)) {
  return makePoint(lhs.x / factor, lhs.y / factor);
}
template <class F1, class F2>
inline auto operator*(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.x * rhs.x + lhs.y * rhs.y) {
  return lhs.x * rhs.x + lhs.y * rhs.y;
}
template <class F1, class F2>
inline auto operator^(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.x * rhs.y - lhs.y * rhs.x) {
  return lhs.x * rhs.y - lhs.y * rhs.x;
}
template <class F1, class F2>
inline auto ccw(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(rhs ^ lhs) {
  return rhs ^ lhs;
}
template <class F1, class F2, class F3>
inline auto ccw(const Point<F1>& lhs, const Point<F2>& rhs,
                const Point<F3>& origin)
    -> decltype(ccw(lhs - origin, rhs - origin)) {
  return ccw(lhs - origin, rhs - origin);
}
template <class F1, class F2>
inline auto operator==(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.x == rhs.x && lhs.y == rhs.y) {
  return lhs.x == rhs.x && lhs.y == rhs.y;
}
template <class F1, class F2>
inline auto operator!=(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(!(lhs == rhs)) {
  return !(lhs == rhs);
}
template <class F1, class F2>
inline auto operator<=(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(!(lhs > rhs)) {
  return !(lhs > rhs);
}
template <class F1, class F2>
inline auto operator<(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.y < rhs.y || (lhs.y == rhs.y && lhs.x < rhs.x)) {
  return lhs.y < rhs.y || (lhs.y == rhs.y && lhs.x < rhs.x);
}
template <class F1, class F2>
inline auto operator>=(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(!(lhs < rhs)) {
  return !(lhs < rhs);
}
template <class F1, class F2>
inline auto operator>(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(rhs < lhs) {
  return rhs < lhs;
}
template <class first>
inline auto angle(const Point<first>& point)
    -> decltype(atan2(point.y, point.x)) {
  return atan2(point.y, point.x);
}
template <class F1, class F2>
inline auto angle(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(atan2(lhs ^ rhs, lhs* rhs)) {
  return atan2(lhs ^ rhs, lhs * rhs);
}
template <class F1, class F2, class F3>
inline auto angle(const Point<F1>& lhs, const Point<F2>& rhs,
                  const Point<F3>& origin)
    -> decltype(angle(lhs - origin, rhs - origin)) {
  return angle(lhs - origin, rhs - origin);
}
template <class F1, class F2, class F3>
inline auto rotate(const Point<F1>& point, const F2& angleSin,
                   const F3& angleCos)
    -> decltype(makePoint(angleCos * point.x - angleSin * point.y,
                          angleSin* point.x + angleCos * point.y)) {
  return makePoint(angleCos * point.x - angleSin * point.y,
                   angleSin * point.x + angleCos * point.y);
}
template <class F1, class F2>
inline auto rotate(const Point<F1>& point, const F2& angle)
    -> decltype(rotate(point, sin(angle), cos(angle))) {
  return rotate(point, sin(angle), cos(angle));
}
template <class F1, class F2, class F3>
inline auto rotate(const Point<F1>& point, const F2& angle,
                   const Point<F3>& origin)
    -> decltype(origin + rotate(point - origin, angle)) {
  return origin + rotate(point - origin, angle);
}
template <class first>
inline auto perp(const Point<first>& point)
    -> decltype(makePoint(-point.y, point.x)) {
  return makePoint(-point.y, point.x);
}
template <class first>
inline auto abs(const Point<first>& point) -> decltype(point * point) {
  return point * point;
}
template <class first>
inline auto norm(const Point<first>& point) -> decltype(sqrt(abs(point))) {
  return sqrt(abs(point));
}
template <class F1, class F2>
inline auto dist(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(norm(lhs - rhs)) {
  return norm(lhs - rhs);
}
template <class F1, class F2>
inline auto dist2(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(abs(lhs - rhs)) {
  return abs(lhs - rhs);
}
template <class F1, class F2>
inline auto bisector(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs * norm(rhs) + rhs * norm(lhs)) {
  return lhs * norm(rhs) + rhs * norm(lhs);
}
template <class first>
bool half(Point<first> p) {
  assert(p.x != 0 || p.y != 0);
  return p.y > 0 || (p.y == 0 && p.x < 0);
}
template <class first>
void polarSort(vector<Point<first>>& v, Point<first> o) {
  sort(v.begin(), v.end(), [o](Point<first> v, Point<first> w) {
    return make_tuple(half(v - o), 0) < make_tuple(half(w - o), v - o ^ w - o);
  });
}
template <class first>
struct Line {
  Point<first> a, ab;
  Line() : a(), ab() {}
  Line(const Point<first>& a, const Point<first>& b, bool twoPoints = true)
      : a(a), ab(twoPoints ? b - a : b) {}
  Line(const first& xa, const first& ya, const first& xb, const first& yb)
      : a(xa, ya), ab(xb - xa, yb - ya) {}
  void swap(Line& other) {
    using std::swap;
    swap(a, other.a);
    swap(ab, other.ab);
  }
  template <class F1>
  explicit operator Line<F1>() const {
    return Line<F1>(Point<F1>(a), Point<F1>(ab), false);
  }
  template <class F1>
  Line& operator=(const Line<F1>& other) {
    a = other.a;
    ab = other.ab;
    return *this;
  }
  Point<first> b() const { return a + ab; }
  operator bool() const { return ab != Point<first>(); }
};
template <class first>
inline Line<first> makeLine(lli a, lli b, lli c) {
  if (a == 0)
    return makeLine(Point<first>(0, -1.0 * c / b),
                    Point<first>(1, -1.0 * c / b));
  else if (b == 0)
    return makeLine(Point<first>(-1.0 * c / a, 0),
                    Point<first>(-1.0 * c / a, 1));
  else
    return makeLine(Point<first>(0, -1.0 * (c) / b),
                    Point<first>(1, -1.0 * (a + c) / b));
}
template <class first>
inline Line<first> makeLine(const Point<first>& a, const Point<first>& b,
                            bool twoPoints = true) {
  return Line<first>(a, b, twoPoints);
}
template <class first>
void swap(Line<first>& lhs, Line<first>& rhs) {
  lhs.swap(rhs);
}
template <class F1, class F2>
bool onLine(const Point<F1>& point, const Line<F2>& line) {
  if (!line) return point == line.a;
  return ((point - line.a) ^ line.ab) == 0;
}
template <class F1, class F2>
bool onSegment(const Point<F1>& point, const Line<F2>& seg) {
  if (!seg) return point == seg.a;
  auto vecta = seg.a - point, vectb = seg.b() - point;
  return (vecta ^ vectb) == 0 && (vecta * vectb) <= 0;
}
template <class F1, class F2>
using distF = decltype(sqrt(F1() + F2()));
template <class F1, class F2>
distF<F1, F2> distLine(const Point<F1>& point, const Line<F2>& line) {
  if (!line) return dist(point, line.a);
  return abs((point - line.a) ^ line.ab) / norm(line.ab);
}
template <class F1, class F2>
distF<F1, F2> distRay(const Point<F1>& point, const Line<F2>& ray) {
  if (((point - ray.a) * ray.ab) <= 0) return dist(point, ray.a);
  return distLine(point, ray);
}
template <class F1, class F2>
distF<F1, F2> distSegment(const Point<F1>& point, const Line<F2>& seg) {
  if (((point - seg.a) * seg.ab) <= 0) return dist(point, seg.a);
  if (((point - seg.b()) * seg.ab) >= 0) return dist(point, seg.b());
  return distLine(point, seg);
}
template <class F1, class F2, class F3>
void projection(const Point<F1>& point, const Line<F2>& line, Point<F3>& res) {
  res = line.a;
  if (line)
    res += line.ab * static_cast<F3>((point - line.a) * line.ab) / abs(line.ab);
}
template <class F1, class F2, class F3>
void closest(const Point<F1>& point, const Line<F2>& seg, Point<F3>& res) {
  if (((point - seg.a) * seg.ab) <= 0)
    res = seg.a;
  else if (((point - seg.b()) * seg.ab) >= 0)
    res = seg.b();
  else
    projection(point, seg, res);
}
template <int TYPE>
struct EndpointChecker {};
template <>
struct EndpointChecker<0> {
  template <class first>
  bool operator()(const first& a, const first& b) const {
    return true;
  }
};
template <>
struct EndpointChecker<1> {
  template <class first>
  bool operator()(const first& a, const first& b) const {
    return a <= b;
  }
};
template <>
struct EndpointChecker<2> {
  template <class first>
  bool operator()(const first& a, const first& b) const {
    return a < b;
  }
};
template <int LA, int LB, int RA, int RB, class F1, class F2, class F3>
bool intersectLines(const Line<F1>& lhs, const Line<F2>& rhs, Point<F3>& res) {
  assert(lhs && rhs);
  auto s = lhs.ab ^ 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;
  bool intersect = EndpointChecker<LA>()(decltype(ls)(0), ls) &&
                   EndpointChecker<LB>()(ls, s) &&
                   EndpointChecker<RA>()(decltype(rs)(0), rs) &&
                   EndpointChecker<RB>()(rs, s);
  if (intersect) res = lhs.a + lhs.ab * static_cast<F3>(ls) / s;
  return intersect;
}
template <class F1, class F2, class F3>
bool intersectClosedSegments(const Line<F1>& lhs, const Line<F2>& rhs,
                             Point<F3>& res) {
  return intersectLines<1, 1, 1, 1>(lhs, rhs, res);
}
template <class F1, class F2, class F3>
bool intersectRays(const Line<F1>& lhs, const Line<F2>& rhs, Point<F3>& res) {
  return intersectLines<1, 0, 1, 0>(lhs, rhs, res);
}
template <class first>
using Polygon = vector<Point<first>>;
inline int prev(int i, int n) { return i == 0 ? n - 1 : i - 1; }
inline int next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
template <class T>
inline int sgn(const T& x) {
  return (T(0) < x) - (x < T(0));
}
template <class first>
bool orientation(const Polygon<first>& poly) {
  int n = static_cast<int>(poly.size());
  int i = static_cast<int>(min_element(begin(poly), end(poly)) - begin(poly));
  return ccw(poly[prev(i, n)], poly[next(i, n)], poly[i]) > 0;
}
template <class first>
first area(const Polygon<first>& poly) {
  int n = static_cast<int>(poly.size());
  first area = first(0);
  for (int i = 0; i < n; ++i)
    area += poly[i].x * (poly[next(i, n)].y - poly[prev(i, n)].y);
  return area;
}
template <class first>
Polygon<first> convexHull(Polygon<first> points) {
  sort(begin(points), end(points));
  Polygon<first> hull;
  hull.reserve(points.size() + 1);
  for (int phase = 0; phase < 2; ++phase) {
    auto start = hull.size();
    for (auto& point : points) {
      while (hull.size() >= start + 2 &&
             ccw(point, hull.back(), hull[hull.size() - 2]) <= 0)
        hull.pop_back();
      hull.push_back(point);
    }
    hull.pop_back();
    reverse(begin(points), end(points));
  }
  if (hull.size() == 2 && hull[0] == hull[1]) hull.pop_back();
  return hull;
}
template <class F1, class F2>
int pointVsConvexPolygon(const Point<F1>& point, const Polygon<F2>& poly,
                         int top) {
  if (point < poly[0] || point > poly[top]) return 1;
  auto orientation = ccw(point, poly[top], poly[0]);
  if (orientation == 0) {
    if (point == poly[0] || point == poly[top]) return 0;
    return top == 1 || top + 1 == poly.size() ? 0 : -1;
  } else if (orientation < 0) {
    auto itRight = lower_bound(begin(poly) + 1, begin(poly) + top, point);
    return sgn(ccw(itRight[0], point, itRight[-1]));
  } else {
    auto itLeft = upper_bound(poly.rbegin(), poly.rend() - top - 1, point);
    return sgn(
        ccw(itLeft == poly.rbegin() ? poly[0] : itLeft[-1], point, itLeft[0]));
  }
}
template <class F1, class F2>
int pointVsPolygon(const Point<F1>& point, const Polygon<F2>& poly) {
  int n = static_cast<int>(poly.size()), windingNumber = 0;
  for (int i = 0; i < n; ++i) {
    if (point == poly[i]) return 0;
    int j = next(i, n);
    if (poly[i].y == point.y && poly[j].y == point.y) {
      if (min(poly[i].x, poly[j].x) <= point.x &&
          point.x <= max(poly[i].x, poly[j].x))
        return 0;
    } else {
      bool below = poly[i].y < point.y;
      if (below != (poly[j].y < point.y)) {
        auto orientation = ccw(point, poly[j], poly[i]);
        if (orientation == 0) return 0;
        if (below == (orientation > 0)) windingNumber += below ? 1 : -1;
      }
    }
  }
  return windingNumber == 0 ? 1 : -1;
}
template <class first, class Function>
int extremeVertex(const Polygon<first>& poly, Function direction) {
  int n = static_cast<int>(poly.size()), left = 0, leftSgn;
  auto vertexCmp = [&poly, direction](int i, int j) {
    return sgn(ccw(direction(poly[j]), poly[j] - poly[i]));
  };
  auto isExtreme = [n, vertexCmp](int i, int& iSgn) {
    return (iSgn = vertexCmp(next(i, n), i)) >= 0 &&
           vertexCmp(i, prev(i, n)) < 0;
  };
  for (int right = isExtreme(0, leftSgn) ? 1 : n; left + 1 < right;) {
    int middle = (left + right) / 2, middleSgn;
    if (isExtreme(middle, middleSgn)) return middle;
    if (leftSgn != middleSgn ? leftSgn < middleSgn
                             : leftSgn == vertexCmp(left, middle))
      right = middle;
    else
      left = middle, leftSgn = middleSgn;
  }
  return left;
}
template <class F1, class F2>
pair<int, int> tangentsConvex(const Point<F1>& point, const Polygon<F2>& poly) {
  return {
      extremeVertex(poly, [&point](const Point<F2>& q) { return q - point; }),
      extremeVertex(poly, [&point](const Point<F2>& q) { return point - q; })};
}
template <class F1, class F2, class F3>
bool stabConvexPolygon(const Line<F1>& line, const Polygon<F2>& poly,
                       Line<F3>& res) {
  assert(line);
  int right =
      extremeVertex(poly, [&line](const Point<F2>&) { return line.ab; });
  int left =
      extremeVertex(poly, [&line](const Point<F2>&) { return -line.ab; });
  auto vertexCmp = [&line](const Point<F2>& vertex) {
    return sgn(ccw(line.ab, vertex - line.a));
  };
  int rightSgn = vertexCmp(poly[right]), leftSgn = vertexCmp(poly[left]);
  if (rightSgn < 0 || leftSgn > 0) return false;
  auto intersectChain = [&line, &poly, vertexCmp](
                            int first, int last, int firstSgn, Point<F3>& res) {
    int n = static_cast<int>(poly.size());
    while (next(first, n) != last) {
      int middle = (first + last + (first < last ? 0 : n)) / 2;
      if (middle >= n) middle -= n;
      if (vertexCmp(poly[middle]) == firstSgn)
        first = middle;
      else
        last = middle;
    }
    intersectLines<0, 0, 0, 0>(line, makeLine(poly[first], poly[last]), res);
  };
  intersectChain(left, right, leftSgn, res.a);
  intersectChain(right, left, rightSgn, res.ab);
  res.ab -= res.a;
  return true;
}
template <class F1, class F2, class first = distF<F1, F2>>
first stabPolygonLength(const Line<F1>& line, Polygon<F2>& poly) {
  assert(line);
  if (!orientation(poly)) reverse(poly.begin() + 1, poly.end());
  first tSum = first(0);
  int n = static_cast<int>(poly.size());
  auto vertexSgn = [&line, &poly](int i) {
    return sgn(line.ab ^ (poly[i] - line.a));
  };
  int prevSgn = vertexSgn(n - 1), iSgn = vertexSgn(0), nextSgn;
  for (int i = 0; i < n; ++i, prevSgn = iSgn, iSgn = nextSgn) {
    nextSgn = vertexSgn(next(i, n));
    if (iSgn == 0) {
      if (prevSgn == 0) {
        if (nextSgn != 0 &&
            nextSgn == sgn((poly[i] - poly[prev(i, n)]) * line.ab))
          tSum += nextSgn * static_cast<first>((poly[i] - line.a) * line.ab) /
                  abs(line.ab);
      } else {
        if ((nextSgn != 0 && nextSgn != prevSgn) ||
            (nextSgn == 0 &&
             prevSgn == sgn((poly[next(i, n)] - poly[i]) * line.ab)))
          tSum -= prevSgn * static_cast<first>((poly[i] - line.a) * line.ab) /
                  abs(line.ab);
      }
    } else if (nextSgn == -iSgn) {
      auto vect = poly[next(i, n)] - poly[i];
      tSum += nextSgn * static_cast<first>((poly[i] - line.a) ^ vect) /
              (line.ab ^ vect);
    }
  }
  return tSum * norm(line.ab);
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  Polygon<ld> mypol(n);
  for (lli i = 0; i < (n); i++) {
    cin >> mypol[i];
  }
  for (lli i = 0; i < (m); i++) {
    Point<ld> p1, p2;
    cin >> p1 >> p2;
    Line<ld> curline(p2, p1);
    cout << fixed << setprecision(20)
         << stabPolygonLength<ld, ld, ld>(curline, mypol) << '\n';
  }
}