#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:10000000000")
#pragma GCC optimize("O3")
using namespace std;
const long double eps = 1e-6;
const long double PI = acosl(-1.0);
struct Point {
  long double x, y;
  Point() : x(0), y(0) {}
  Point(long double x, long double y) : x(x), y(y) {}
  Point(const Point &a) : x(a.x), y(a.y) {}
  Point(const Point &a, const Point &b) : x(b.x - a.x), y(b.y - a.y) {}
  long double len() const { return sqrtl(x * x + y * y); }
  long double distanceTo(const Point &that) const {
    return Point(*this, that).len();
  }
  bool operator<(const Point &that) const {
    if (x != that.x) return x < that.x;
    return y < that.y;
  }
  Point operator-(const Point &that) const {
    return Point(x - that.x, y - that.y);
  }
  long double dotProduct(const Point &that) const {
    return x * that.x + y * that.y;
  }
  bool isOrthogonalTo(const Point &that) const {
    return fabsl(dotProduct(that)) < eps;
  }
  Point orthogonalPoint() const { return Point(-y, x); }
  long double crossProduct(const Point &that) const {
    return x * that.y - y * that.x;
  }
  bool isCollinearTo(const Point &that) const {
    return fabsl(crossProduct(that)) < eps;
  }
};
struct Line {
  long double a, b, c;
  Line() {}
  Line(long double a, long double b, long double c) : a(a), b(b), c(c) {}
  Line(const Point &p1, const Point &p2)
      : a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}
  Point normal() const { return Point(a, b); }
  long double distanceTo(const Point &p) const {
    return fabsl(a * p.x + b * p.y + c) / sqrtl(a * a + b * b);
  }
  int side(const Point &p) const {
    long double r = (a * p.x + b * p.y + c) / sqrtl(a * a + b * b);
    if (fabsl(r) < eps)
      return 0;
    else
      return r > 0 ? 1 : -1;
  }
  bool has(const Point &p) const { return side(p) == 0; }
  long double distanceTo(const Line &that) const {
    if (normal().isCollinearTo(that.normal())) {
      Point p = (fabsl(a) < eps ? Point(0, -c / b) : Point(-c / a, 0));
      return that.distanceTo(p);
    } else
      return 0;
  }
  bool intersectsWith(const Line &that) const { return distanceTo(that) < eps; }
  Point intersection(const Line &that) const {
    long double d = a * that.b - b * that.a;
    long double dx = -c * that.b - b * -that.c;
    long double dy = a * -that.c - -c * that.a;
    return Point(dx / d, dy / d);
  }
};
struct Segment {
  Point p1, p2;
  long double a, b, c;
  Segment() {}
  Segment(const Point &p1, const Point &p2)
      : p1(p1),
        p2(p2),
        a(p1.y - p2.y),
        b(p2.x - p1.x),
        c(p1.x * p2.y - p2.x * p1.y) {}
  long double distanceTo(const Point &p) const {
    if (Point(p1, p).dotProduct(Point(p1, p2)) >= -eps &&
        Point(p2, p).dotProduct(Point(p2, p1)) >= -eps)
      return fabsl(a * p.x + b * p.y + c) / sqrtl(a * a + b * b);
    else
      return min(p1.distanceTo(p), p2.distanceTo(p));
  }
  bool has(const Point &p) const { return distanceTo(p) < eps; }
  bool intersectsWith(const Line &that) const {
    Line l(a, b, c);
    if (l.intersectsWith(that)) {
      Point p = l.intersection(that);
      if (has(p)) return 1;
    }
    return 0;
  }
  Point intersection(const Line &that) const {
    Line l(a, b, c);
    return l.intersection(that);
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<Point> p(n);
  vector<Segment> s;
  for (int i = 0; i < n; ++i) cin >> p[i].x >> p[i].y;
  for (int i = 1; i < n; ++i) {
    s.push_back(Segment(p[i - 1], p[i]));
  }
  s.push_back(Segment(p.back(), p[0]));
  for (int rep_iter = 0; rep_iter < m; ++rep_iter) {
    long double ans = 0;
    Point a, b;
    cin >> a.x >> a.y >> b.x >> b.y;
    Line ln(a, b);
    vector<Segment> onLine;
    vector<Point> interLine;
    for (int i = 0; i < n; ++i) {
      if (ln.has(s[i].p1) && ln.has(s[i].p2)) {
        onLine.push_back(s[i]);
        continue;
      }
      if (!ln.has(s[i].p1) && !ln.has(s[i].p2) && s[i].intersectsWith(ln)) {
        interLine.push_back(s[i].intersection(ln));
        continue;
      }
    }
    for (int i = 0; i < n;) {
      if (ln.side(s[i].p1) && !ln.side(s[i].p2)) {
        int side = ln.side(s[i].p1);
        Point p1 = s[i].p2;
        int j = (i + 1) % n;
        while (!ln.side(s[j].p2)) j = (j + 1) % n;
        if (ln.side(s[j].p2) != side) {
          interLine.push_back(p1);
        }
        if (j <= i) break;
        i = j;
      }
      ++i;
    }
    sort(begin(interLine), end(interLine));
    for (auto &i : onLine)
      if (i.p2 < i.p1) swap(i.p1, i.p2);
    for (int i = 1; i < interLine.size(); i += 2)
      onLine.push_back({interLine[i - 1], interLine[i]});
    sort(begin(onLine), end(onLine),
         [](const Segment &a, const Segment &b) { return a.p1 < b.p1; });
    vector<Segment> res;
    if (onLine.size()) {
      Segment cur = onLine[0];
      for (int i = 1; i < onLine.size(); ++i) {
        if (onLine[i].p1 < cur.p2) {
          cur.p2 = max(cur.p2, onLine[i].p2);
        } else {
          ans += (cur.p2 - cur.p1).len();
          cur = onLine[i];
        }
      }
      ans += (cur.p2 - cur.p1).len();
    }
    cout << fixed << setprecision(10) << ans << '\n';
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:10000000000")
#pragma GCC optimize("O3")
using namespace std;
const long double eps = 1e-6;
const long double PI = acosl(-1.0);
struct Point {
  long double x, y;
  Point() : x(0), y(0) {}
  Point(long double x, long double y) : x(x), y(y) {}
  Point(const Point &a) : x(a.x), y(a.y) {}
  Point(const Point &a, const Point &b) : x(b.x - a.x), y(b.y - a.y) {}
  long double len() const { return sqrtl(x * x + y * y); }
  long double distanceTo(const Point &that) const {
    return Point(*this, that).len();
  }
  bool operator<(const Point &that) const {
    if (x != that.x) return x < that.x;
    return y < that.y;
  }
  Point operator-(const Point &that) const {
    return Point(x - that.x, y - that.y);
  }
  long double dotProduct(const Point &that) const {
    return x * that.x + y * that.y;
  }
  bool isOrthogonalTo(const Point &that) const {
    return fabsl(dotProduct(that)) < eps;
  }
  Point orthogonalPoint() const { return Point(-y, x); }
  long double crossProduct(const Point &that) const {
    return x * that.y - y * that.x;
  }
  bool isCollinearTo(const Point &that) const {
    return fabsl(crossProduct(that)) < eps;
  }
};
struct Line {
  long double a, b, c;
  Line() {}
  Line(long double a, long double b, long double c) : a(a), b(b), c(c) {}
  Line(const Point &p1, const Point &p2)
      : a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}
  Point normal() const { return Point(a, b); }
  long double distanceTo(const Point &p) const {
    return fabsl(a * p.x + b * p.y + c) / sqrtl(a * a + b * b);
  }
  int side(const Point &p) const {
    long double r = (a * p.x + b * p.y + c) / sqrtl(a * a + b * b);
    if (fabsl(r) < eps)
      return 0;
    else
      return r > 0 ? 1 : -1;
  }
  bool has(const Point &p) const { return side(p) == 0; }
  long double distanceTo(const Line &that) const {
    if (normal().isCollinearTo(that.normal())) {
      Point p = (fabsl(a) < eps ? Point(0, -c / b) : Point(-c / a, 0));
      return that.distanceTo(p);
    } else
      return 0;
  }
  bool intersectsWith(const Line &that) const { return distanceTo(that) < eps; }
  Point intersection(const Line &that) const {
    long double d = a * that.b - b * that.a;
    long double dx = -c * that.b - b * -that.c;
    long double dy = a * -that.c - -c * that.a;
    return Point(dx / d, dy / d);
  }
};
struct Segment {
  Point p1, p2;
  long double a, b, c;
  Segment() {}
  Segment(const Point &p1, const Point &p2)
      : p1(p1),
        p2(p2),
        a(p1.y - p2.y),
        b(p2.x - p1.x),
        c(p1.x * p2.y - p2.x * p1.y) {}
  long double distanceTo(const Point &p) const {
    if (Point(p1, p).dotProduct(Point(p1, p2)) >= -eps &&
        Point(p2, p).dotProduct(Point(p2, p1)) >= -eps)
      return fabsl(a * p.x + b * p.y + c) / sqrtl(a * a + b * b);
    else
      return min(p1.distanceTo(p), p2.distanceTo(p));
  }
  bool has(const Point &p) const { return distanceTo(p) < eps; }
  bool intersectsWith(const Line &that) const {
    Line l(a, b, c);
    if (l.intersectsWith(that)) {
      Point p = l.intersection(that);
      if (has(p)) return 1;
    }
    return 0;
  }
  Point intersection(const Line &that) const {
    Line l(a, b, c);
    return l.intersection(that);
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<Point> p(n);
  vector<Segment> s;
  for (int i = 0; i < n; ++i) cin >> p[i].x >> p[i].y;
  for (int i = 1; i < n; ++i) {
    s.push_back(Segment(p[i - 1], p[i]));
  }
  s.push_back(Segment(p.back(), p[0]));
  for (int rep_iter = 0; rep_iter < m; ++rep_iter) {
    long double ans = 0;
    Point a, b;
    cin >> a.x >> a.y >> b.x >> b.y;
    Line ln(a, b);
    vector<Segment> onLine;
    vector<Point> interLine;
    for (int i = 0; i < n; ++i) {
      if (ln.has(s[i].p1) && ln.has(s[i].p2)) {
        onLine.push_back(s[i]);
        continue;
      }
      if (!ln.has(s[i].p1) && !ln.has(s[i].p2) && s[i].intersectsWith(ln)) {
        interLine.push_back(s[i].intersection(ln));
        continue;
      }
    }
    for (int i = 0; i < n;) {
      if (ln.side(s[i].p1) && !ln.side(s[i].p2)) {
        int side = ln.side(s[i].p1);
        Point p1 = s[i].p2;
        int j = (i + 1) % n;
        while (!ln.side(s[j].p2)) j = (j + 1) % n;
        if (ln.side(s[j].p2) != side) {
          interLine.push_back(p1);
        }
        if (j <= i) break;
        i = j;
      }
      ++i;
    }
    sort(begin(interLine), end(interLine));
    for (auto &i : onLine)
      if (i.p2 < i.p1) swap(i.p1, i.p2);
    for (int i = 1; i < interLine.size(); i += 2)
      onLine.push_back({interLine[i - 1], interLine[i]});
    sort(begin(onLine), end(onLine),
         [](const Segment &a, const Segment &b) { return a.p1 < b.p1; });
    vector<Segment> res;
    if (onLine.size()) {
      Segment cur = onLine[0];
      for (int i = 1; i < onLine.size(); ++i) {
        if (onLine[i].p1 < cur.p2) {
          cur.p2 = max(cur.p2, onLine[i].p2);
        } else {
          ans += (cur.p2 - cur.p1).len();
          cur = onLine[i];
        }
      }
      ans += (cur.p2 - cur.p1).len();
    }
    cout << fixed << setprecision(10) << ans << '\n';
  }
  return 0;
}

```