#include <bits/stdc++.h>
using namespace std;
using float_type = long double;
float_type EPS = 1e-7;
constexpr float_type pi = 3.1415926535897932384626433832795L;
struct point;
struct vec;
struct line;
struct segment;
struct point {
  float_type x, y;
  point() {}
  point(float_type xn, float_type yn) : x(xn), y(yn) {}
  inline float_type dist_to(point dest) const {
    return hypot(dest.x - x, dest.y - y);
  }
  inline float_type dist_to(line l) const;
  inline bool operator==(const point &p) const {
    return (abs(x - p.x) <= EPS) && (abs(y - p.y) <= EPS);
  }
  inline bool operator<(const point &p) const {
    return x < (p.x - EPS) || (abs(x - p.x) <= EPS && y < (p.y - EPS));
  }
  inline bool inside_angle(const point &p1, const point &p2,
                           const point &s) const;
  inline float_type dist_to(const segment &s) const;
  inline bool on(const line &l) const;
  inline bool on(const segment &s) const;
};
struct vec {
  float_type x, y;
  vec() {}
  vec(float_type xn, float_type yn) : x(xn), y(yn) {}
  vec(point a, point b) : x(b.x - a.x), y(b.y - a.y) {}
  inline vec operator+(const vec &v) const { return vec(x + v.x, y + v.y); }
  inline vec operator-(const vec &v) const { return vec(x - v.x, y - v.y); }
  inline vec operator*(const float_type &c) const { return vec(x * c, y * c); }
  inline float_type operator*(const vec &v) const { return x * v.x + y * v.y; }
  inline float_type operator^(const vec &v) const { return x * v.y - y * v.x; }
  inline float_type length() const { return hypot(x, y); }
};
inline point operator+(const point &p, const vec &v) {
  return point(p.x + v.x, p.y + v.y);
}
inline point operator-(const point &p, const vec &v) {
  return point(p.x - v.x, p.y - v.y);
}
struct line {
  float_type a, b, c;
  line() {}
  line(float_type an, float_type bn, float_type cn) : a(an), b(bn), c(cn) {
    normalize();
  }
  line(point p1, point p2)
      : a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {
    normalize();
  }
  line(point p, vec v) : line(p, p + v) {}
  line(segment s);
  inline void normalize() {
    float_type sign = (abs(a) <= EPS) ? b / abs(b) : a / abs(a);
    float_type d = sqrt(a * a + b * b) * sign;
    a /= d;
    b /= d;
    c /= d;
  }
  inline point intersect(line l) const {
    return point((b * l.c - l.b * c) / (a * l.b - l.a * b),
                 (a * l.c - l.a * c) / (b * l.a - l.b * a));
  }
  inline bool parallel(line l) const {
    return abs(a - l.a) <= EPS && abs(b - l.b) <= EPS && abs(c - l.c) > EPS;
  }
  inline bool operator==(line l) const {
    return abs(a - l.a) <= EPS && abs(b - l.b) <= EPS && abs(c - l.c) <= EPS;
  }
};
inline float_type point::dist_to(line l) const {
  return abs(l.a * x + l.b * y + l.c);
}
inline bool point::inside_angle(const point &p1, const point &p2,
                                const point &s) const {
  return (vec(s, p1) ^ vec(s, *this)) >= -EPS &&
         (vec(s, *this) ^ vec(s, p2)) >= -EPS;
}
struct segment {
  point a, b;
  segment() {}
  segment(point an, point bn) : a(an), b(bn) {}
  segment(float_type x1, float_type y1, float_type x2, float_type y2)
      : segment(point(x1, y1), point(x2, y2)) {}
  inline float_type length() const { return a.dist_to(b); }
  inline float_type dist_to(const segment &s) const;
  inline segment shift(const vec &v) const { return segment(a + v, b + v); }
  inline bool on(const line &l) const { return a.on(l) && b.on(l); }
};
line::line(segment s) : line(s.a, s.b) {}
inline bool point::on(const line &l) const {
  return abs(l.a * x + l.b * y + l.c) <= EPS;
}
inline bool point::on(const segment &s) const {
  return on(line(s)) && abs(s.length() - dist_to(s.a) - dist_to(s.b)) <= EPS;
}
inline float_type point::dist_to(const segment &s) const {
  if (vec(s.a, s.b) * vec(s.a, *this) <= EPS) {
    return dist_to(s.a);
  } else if (vec(s.b, s.a) * vec(s.b, *this) <= EPS) {
    return dist_to(s.b);
  } else {
    return dist_to(line(s));
  }
}
inline float_type segment::dist_to(const segment &s) const {
  point i = line(*this).intersect(line(s));
  if (i.on(s) && i.on(*this)) {
    return 0.0;
  } else {
    return min(min((this->a).dist_to(s), (this->b).dist_to(s)),
               min((s.a).dist_to(*this), (s.b).dist_to(*this)));
  }
}
inline float_type angle(const vec &v, const vec &u) {
  return atan2(v ^ u, v * u);
}
using polygon = vector<point>;
int main() {
  using namespace rel_ops;
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(7);
  int32_t n, m;
  cin >> n >> m;
  polygon poly1(n);
  for (auto &p : poly1) {
    cin >> p.x >> p.y;
  }
  polygon poly;
  poly.reserve(n);
  for (int32_t i = 0; i < n; ++i) {
    int32_t pr = (i + n - 1) % n, ne = (i + 1) % n;
    if (abs(vec(poly1[pr], poly1[i]) ^ vec(poly1[i], poly1[ne])) > EPS) {
      poly.push_back(poly1[i]);
    }
  }
  n = (int32_t)poly.size();
  float_type agl = 0;
  for (int32_t i = 0; i < n; ++i) {
    int32_t pr = (i + n - 1) % n, ne = (i + 1) % n;
    agl += angle(vec(poly[pr], poly[i]), vec(poly[i], poly[ne]));
  }
  if (agl < 0) {
    reverse(poly.begin(), poly.end());
  }
  for (int32_t i = 0; i < m; ++i) {
    point p1, p2;
    cin >> p1.x >> p1.y >> p2.x >> p2.y;
    line l = line(p1, p2);
    vector<point> ps;
    point pr = poly[n - 1], c = poly[0], ne = poly[1];
    for (int32_t j = 0; j < n; ++j) {
      if ((pr.on(l) && c.on(l)) || (c.on(l) && ne.on(l))) {
        if ((vec(pr, c) ^ vec(c, ne)) > 0) {
          ps.push_back(c);
        }
      } else if (c.on(l)) {
        if (l.intersect(line(pr, ne)).on(segment(pr, ne))) {
          ps.push_back(c);
        }
      } else {
        point y = l.intersect(line(pr, c));
        if (y.on(segment(pr, c)) && y != pr) {
          ps.push_back(l.intersect(line(pr, c)));
        }
      }
      pr = c;
      c = ne;
      ne = poly[(j + 2) % n];
    }
    sort(ps.begin(), ps.end());
    float_type res = 0;
    for (int32_t k = 0; k + 1 < (int32_t)ps.size(); k += 2) {
      res += ps[k].dist_to(ps[k + 1]);
    }
    cout << res << endl;
  }
  return 0;
}

### Prompt

Generate a cpp solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using float_type = long double;
float_type EPS = 1e-7;
constexpr float_type pi = 3.1415926535897932384626433832795L;
struct point;
struct vec;
struct line;
struct segment;
struct point {
  float_type x, y;
  point() {}
  point(float_type xn, float_type yn) : x(xn), y(yn) {}
  inline float_type dist_to(point dest) const {
    return hypot(dest.x - x, dest.y - y);
  }
  inline float_type dist_to(line l) const;
  inline bool operator==(const point &p) const {
    return (abs(x - p.x) <= EPS) && (abs(y - p.y) <= EPS);
  }
  inline bool operator<(const point &p) const {
    return x < (p.x - EPS) || (abs(x - p.x) <= EPS && y < (p.y - EPS));
  }
  inline bool inside_angle(const point &p1, const point &p2,
                           const point &s) const;
  inline float_type dist_to(const segment &s) const;
  inline bool on(const line &l) const;
  inline bool on(const segment &s) const;
};
struct vec {
  float_type x, y;
  vec() {}
  vec(float_type xn, float_type yn) : x(xn), y(yn) {}
  vec(point a, point b) : x(b.x - a.x), y(b.y - a.y) {}
  inline vec operator+(const vec &v) const { return vec(x + v.x, y + v.y); }
  inline vec operator-(const vec &v) const { return vec(x - v.x, y - v.y); }
  inline vec operator*(const float_type &c) const { return vec(x * c, y * c); }
  inline float_type operator*(const vec &v) const { return x * v.x + y * v.y; }
  inline float_type operator^(const vec &v) const { return x * v.y - y * v.x; }
  inline float_type length() const { return hypot(x, y); }
};
inline point operator+(const point &p, const vec &v) {
  return point(p.x + v.x, p.y + v.y);
}
inline point operator-(const point &p, const vec &v) {
  return point(p.x - v.x, p.y - v.y);
}
struct line {
  float_type a, b, c;
  line() {}
  line(float_type an, float_type bn, float_type cn) : a(an), b(bn), c(cn) {
    normalize();
  }
  line(point p1, point p2)
      : a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {
    normalize();
  }
  line(point p, vec v) : line(p, p + v) {}
  line(segment s);
  inline void normalize() {
    float_type sign = (abs(a) <= EPS) ? b / abs(b) : a / abs(a);
    float_type d = sqrt(a * a + b * b) * sign;
    a /= d;
    b /= d;
    c /= d;
  }
  inline point intersect(line l) const {
    return point((b * l.c - l.b * c) / (a * l.b - l.a * b),
                 (a * l.c - l.a * c) / (b * l.a - l.b * a));
  }
  inline bool parallel(line l) const {
    return abs(a - l.a) <= EPS && abs(b - l.b) <= EPS && abs(c - l.c) > EPS;
  }
  inline bool operator==(line l) const {
    return abs(a - l.a) <= EPS && abs(b - l.b) <= EPS && abs(c - l.c) <= EPS;
  }
};
inline float_type point::dist_to(line l) const {
  return abs(l.a * x + l.b * y + l.c);
}
inline bool point::inside_angle(const point &p1, const point &p2,
                                const point &s) const {
  return (vec(s, p1) ^ vec(s, *this)) >= -EPS &&
         (vec(s, *this) ^ vec(s, p2)) >= -EPS;
}
struct segment {
  point a, b;
  segment() {}
  segment(point an, point bn) : a(an), b(bn) {}
  segment(float_type x1, float_type y1, float_type x2, float_type y2)
      : segment(point(x1, y1), point(x2, y2)) {}
  inline float_type length() const { return a.dist_to(b); }
  inline float_type dist_to(const segment &s) const;
  inline segment shift(const vec &v) const { return segment(a + v, b + v); }
  inline bool on(const line &l) const { return a.on(l) && b.on(l); }
};
line::line(segment s) : line(s.a, s.b) {}
inline bool point::on(const line &l) const {
  return abs(l.a * x + l.b * y + l.c) <= EPS;
}
inline bool point::on(const segment &s) const {
  return on(line(s)) && abs(s.length() - dist_to(s.a) - dist_to(s.b)) <= EPS;
}
inline float_type point::dist_to(const segment &s) const {
  if (vec(s.a, s.b) * vec(s.a, *this) <= EPS) {
    return dist_to(s.a);
  } else if (vec(s.b, s.a) * vec(s.b, *this) <= EPS) {
    return dist_to(s.b);
  } else {
    return dist_to(line(s));
  }
}
inline float_type segment::dist_to(const segment &s) const {
  point i = line(*this).intersect(line(s));
  if (i.on(s) && i.on(*this)) {
    return 0.0;
  } else {
    return min(min((this->a).dist_to(s), (this->b).dist_to(s)),
               min((s.a).dist_to(*this), (s.b).dist_to(*this)));
  }
}
inline float_type angle(const vec &v, const vec &u) {
  return atan2(v ^ u, v * u);
}
using polygon = vector<point>;
int main() {
  using namespace rel_ops;
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(7);
  int32_t n, m;
  cin >> n >> m;
  polygon poly1(n);
  for (auto &p : poly1) {
    cin >> p.x >> p.y;
  }
  polygon poly;
  poly.reserve(n);
  for (int32_t i = 0; i < n; ++i) {
    int32_t pr = (i + n - 1) % n, ne = (i + 1) % n;
    if (abs(vec(poly1[pr], poly1[i]) ^ vec(poly1[i], poly1[ne])) > EPS) {
      poly.push_back(poly1[i]);
    }
  }
  n = (int32_t)poly.size();
  float_type agl = 0;
  for (int32_t i = 0; i < n; ++i) {
    int32_t pr = (i + n - 1) % n, ne = (i + 1) % n;
    agl += angle(vec(poly[pr], poly[i]), vec(poly[i], poly[ne]));
  }
  if (agl < 0) {
    reverse(poly.begin(), poly.end());
  }
  for (int32_t i = 0; i < m; ++i) {
    point p1, p2;
    cin >> p1.x >> p1.y >> p2.x >> p2.y;
    line l = line(p1, p2);
    vector<point> ps;
    point pr = poly[n - 1], c = poly[0], ne = poly[1];
    for (int32_t j = 0; j < n; ++j) {
      if ((pr.on(l) && c.on(l)) || (c.on(l) && ne.on(l))) {
        if ((vec(pr, c) ^ vec(c, ne)) > 0) {
          ps.push_back(c);
        }
      } else if (c.on(l)) {
        if (l.intersect(line(pr, ne)).on(segment(pr, ne))) {
          ps.push_back(c);
        }
      } else {
        point y = l.intersect(line(pr, c));
        if (y.on(segment(pr, c)) && y != pr) {
          ps.push_back(l.intersect(line(pr, c)));
        }
      }
      pr = c;
      c = ne;
      ne = poly[(j + 2) % n];
    }
    sort(ps.begin(), ps.end());
    float_type res = 0;
    for (int32_t k = 0; k + 1 < (int32_t)ps.size(); k += 2) {
      res += ps[k].dist_to(ps[k + 1]);
    }
    cout << res << endl;
  }
  return 0;
}

```