#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ul = unsigned long long;
using db = double;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using pd = pair<ld, ld>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long long>;
using vd = vector<ld>;
using vs = vector<string>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
template <typename T, size_t size>
using va = vector<array<T, size>>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename A, typename B>
istream &operator>>(istream &in, pair<A, B> &p) {
  return in >> p.first >> p.second;
}
template <typename T, size_t size>
ostream &operator<<(ostream &os, const array<T, size> &arr) {
  for (const auto &x : arr) os << x << ' ';
  return os;
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << p.first << " " << p.second;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &vec) {
  for (auto &x : vec) {
    in >> x;
  }
  return in;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (const auto &x : v) os << x << ' ';
  return os;
}
template <class T>
bool ckmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
void debug() { cerr << "\n"; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
  cerr << ' ' << H;
  debug(T...);
}
inline long long modPow(long long x, long long y, long long mod) {
  long long res = 1;
  x = x % mod;
  ;
  while (y > 0) {
    if (y & 1) {
      res = (res * x) % mod;
    }
    y = y >> 1;
    x = (x * x) % mod;
  }
  return res;
}
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
char dirs[4] = {'R', 'D', 'L', 'U'};
unordered_map<char, int> rdirs = {{'R', 0}, {'D', 1}, {'L', 2}, {'U', 3}};
const long long INF = 1e18 + 6;
const long long mod = 1e9 + 7;
const int MXN = 3e6 + 5;
template <typename T>
struct Point {
  T x, y;
  Point() : x(0), y(0) {}
  Point(T _x, T _y) : x(_x), y(_y) {}
  friend istream &operator>>(std::istream &i, Point &p) {
    return i >> p.x >> p.y;
  }
  friend ostream &operator<<(std::ostream &o, const Point &p) {
    return o << "(" << p.x << ", " << p.y << ")";
  }
  Point unitPolar(T ang) {
    auto c = exp(ang * complex<T>(0, 1));
    return P(c.real(), c.imag());
  }
  T norm() const { return x * x + y * y; }
  double abs() const { return sqrt(norm()); }
  double ang() const { return atan2(y, x); }
  Point<T> conj() const { return {x, -y}; }
  Point &operator+=(const Point &o) {
    x += o.x;
    y += o.y;
    return *this;
  }
  Point &operator-=(const Point &o) {
    x -= o.x;
    y -= o.y;
    return *this;
  }
  Point &operator*=(const T &c) {
    x *= c;
    y *= c;
    return *this;
  }
  Point &operator/=(const T &c) {
    x /= c;
    y /= c;
    return *this;
  }
  friend Point operator+(const Point &a, const Point &b) {
    return Point(a) += b;
  }
  friend Point operator-(const Point &a, const Point &b) {
    return Point(a) -= b;
  }
  friend Point operator*(const Point &a, const T &c) { return Point(a) *= c; }
  friend Point operator*(const T &c, const Point &a) { return Point(a) *= c; }
  friend Point operator/(const Point &a, const T &c) { return Point(a) /= c; }
  bool operator==(const Point &o) const { return x == o.x && y == o.y; }
  bool operator!=(const Point &o) const { return x != o.x || y != o.y; }
  bool operator<(const Point &o) const {
    return (x != o.x) ? x < o.x : y < o.y;
  }
  bool operator>(const Point &o) const {
    return (x != o.x) ? x > o.x : y > o.y;
  }
  bool operator<=(const Point &o) const { return !(*this > o); }
  friend T dot(const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; }
  friend T cross(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
  }
  friend T cross(const Point &p, const Point &a, const Point &b) {
    return cross(a - p, b - p);
  }
  friend Point<T> operator*(const Point &a, const Point &b) {
    return {a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x};
  }
  friend Point<T> operator/(const Point &a, const Point &b) {
    return a * b.conj() / b.norm();
  }
  Point unit() const { return Point(*this) / abs(); }
  Point rotate(const double &ang) const {
    return *this * Point(cos(ang), sin(ang));
  }
  double dist(const Point &a) const { return (a - *this).abs(); }
  double dist(const Point &a, const Point &b) {
    return abs(cross(*this, a, b)) / a.dist(b);
  }
  Point reflect(const Point &a, const Point &b) const {
    return a + ((*this - a) / (b - a)).conj() * (b - a);
  }
  Point foot(const Point &a, const Point &b) const {
    return (*this + this->reflect(a, b)) / 2;
  }
  friend Point intersect(const Point &a, const Point &b, const Point &c,
                         const Point &d) {
    T u = cross(a, b, c), v = cross(a, b, d);
    return (d * u - c * v) / (u - v);
  }
  using polygon = std::vector<Point<T>>;
  friend polygon seg_intersect(Point a, Point b, Point c, Point d) {
    if (a > b) swap(a, b);
    if (c > d) swap(c, d);
    T a1 = cross(a, b, c), a2 = cross(a, b, d);
    if (a1 > a2) swap(a1, a2);
    if (!(a1 <= 0 && a2 >= 0)) return {};
    if (a1 == 0 && a2 == 0) {
      if (cross(a, c, d) != 0) return {};
      Point<T> x1 = max(a, c), x2 = min(b, d);
      if (x1 > x2) return {};
      if (x1 == x2) return {x1};
      return {x1, x2};
    }
    Point<T> z = intersect(a, b, c, d);
    if (a <= z && z <= b) return {z};
    return {};
  }
  friend std::ostream &operator<<(std::ostream &o, const polygon &poly) {
    o << "{";
    for (auto pt : poly) o << " " << pt;
    return o << " }";
  }
  enum class Classification { in, out, on };
  Classification classify(const polygon &p) const {
    bool ans = 0;
    for (int i = 0; i < int(p.size()); i++) {
      Point<T> a = p[i], b = p[(i + 1) % p.size()];
      if (cross(a, b, *this) == 0 && min(a, b) <= *this && *this <= max(a, b))
        return Classification::on;
      if (a.y > b.y) swap(a, b);
      if (a.y <= y && y < b.y && cross(*this, a, b) > 0) ans ^= 1;
    }
    return ans ? Classification::in : Classification::out;
  }
  friend polygon convex_hull(const std::vector<Point> &pts) {
    Point pivot = *min_element((pts).begin(), (pts).end());
    auto sorted = pts;
    sort((sorted).begin(), (sorted).end(),
         [&pivot](const Point &p, const Point &q) {
           T cp = cross(pivot, p, q);
           if (cp != 0) return cp > 0;
           return pivot.dist(p) < pivot.dist(q);
         });
    int j = 0;
    polygon res(pts.size());
    for (const Point &p : sorted) {
      while (j > 1 && cross(res[j - 2], res[j - 1], p) <= 0) j--;
      res[j++] = p;
    }
    res.erase(res.begin() + j, res.end());
    return res;
  }
  Point centroid(const vector<Point> &v) {
    Point cen(0, 0);
    T area = 0;
    for (int i = 0; i < int(((int)(v).size())); i++) {
      int j = (i + 1) % ((int)(v).size());
      T a = cross(v[i], v[j]);
      cen += a * (v[i] + v[j]);
      area += a;
    }
    return cen / area / (T)3;
  }
  friend T area(const polygon &p) {
    T a = 0;
    for (int i = 0; i < int(p.size()); i++)
      a += cross(p[i], p[i + 1 < ((int)(p).size()) ? i + 1 : 0]);
    return a;
  }
  template <typename U>
  static int sign(const U &v) {
    return (v > 0) - (v < 0);
  }
  friend int compare_by_angle(const Point &a, const Point &b) {
    return sign(cross(b, a));
  }
  friend int compare_by_angle(const Point &a, const Point &b,
                              const Point &origin) {
    return sign(cross(origin, b, a));
  }
  template <typename I>
  friend void sort_by_angle(I first, I last,
                            const Point<T> &origin = Point<T>{}) {
    first =
        partition(first, last, [&](const Point<T> &p) { return p == origin; });
    auto pivot =
        partition(first, last, [&](const Point<T> &p) { return p > origin; });
    auto compare = [&](const Point<T> &l, const Point<T> &r) {
      return compare_by_angle(l, r, origin) < 0;
    };
    sort(first, pivot, compare);
    sort(pivot, last, compare);
  }
  pair<Point, double> ccCenter(Point a, Point b, Point c) {
    b -= a;
    c -= a;
    Point res = b * c * (c.conj() - b.conj()) / (b * c.conj() - b.conj() * c);
    return {a + res, abs(res)};
  }
  pair<Point, double> mec(vector<Point> ps) {
    shuffle((ps).begin(), (ps).end(), mt19937(time(0)));
    Point o = ps[0];
    double r = 0, EPS = 1 + 1e-8;
    for (int i = 0; i < int(((int)(ps).size())); i++)
      if (abs(o - ps[i]) > r * EPS) {
        o = ps[i], r = 0;
        for (int j = 0; j < int(i); j++)
          if (abs(o - ps[j]) > r * EPS) {
            o = (ps[i] + ps[j]) / 2, r = abs(o - ps[i]);
            for (int k = 0; k < int(j); k++)
              if (abs(o - ps[k]) > r * EPS)
                tie(o, r) = ccCenter(ps[i], ps[j], ps[k]);
          }
      }
    return {o, r};
  }
};
using pt = Point<double>;
void solve() {
  int n, m;
  cin >> n >> m;
  vector<pt> a(n);
  cin >> a;
  if (area(a) < 0) reverse((a).begin(), (a).end());
  while (m--) {
    pt x, y;
    cin >> x >> y;
    ld ans = 0;
    vi sg;
    for (int k = 0; k < int(n); k++) {
      sg.push_back(pt::sign(cross(x, y, a[k])) >= 0);
    }
    for (int i = 0; i < int(n); i++) {
      int j = (i + 1) % n;
      if (sg[i] != sg[j]) {
        ans += pt::sign(cross(a[i] - a[j], y - x)) *
               dot(y - x, intersect(x, y, a[i], a[j]));
      }
      if (cross(x, y, a[i]) == 0 && cross(x, y, a[j]) == 0 &&
          dot(y - x, a[j] - a[i]) > 0) {
        ans += dot(y - x, a[j] - a[i]);
      }
    }
    cout << ans / (x - y).abs() << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  int t = 1, tc = 1;
  while (t--) {
    solve();
    tc++;
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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 ld = long double;
using ul = unsigned long long;
using db = double;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using pd = pair<ld, ld>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long long>;
using vd = vector<ld>;
using vs = vector<string>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
template <typename T, size_t size>
using va = vector<array<T, size>>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename A, typename B>
istream &operator>>(istream &in, pair<A, B> &p) {
  return in >> p.first >> p.second;
}
template <typename T, size_t size>
ostream &operator<<(ostream &os, const array<T, size> &arr) {
  for (const auto &x : arr) os << x << ' ';
  return os;
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << p.first << " " << p.second;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &vec) {
  for (auto &x : vec) {
    in >> x;
  }
  return in;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (const auto &x : v) os << x << ' ';
  return os;
}
template <class T>
bool ckmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
void debug() { cerr << "\n"; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
  cerr << ' ' << H;
  debug(T...);
}
inline long long modPow(long long x, long long y, long long mod) {
  long long res = 1;
  x = x % mod;
  ;
  while (y > 0) {
    if (y & 1) {
      res = (res * x) % mod;
    }
    y = y >> 1;
    x = (x * x) % mod;
  }
  return res;
}
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
char dirs[4] = {'R', 'D', 'L', 'U'};
unordered_map<char, int> rdirs = {{'R', 0}, {'D', 1}, {'L', 2}, {'U', 3}};
const long long INF = 1e18 + 6;
const long long mod = 1e9 + 7;
const int MXN = 3e6 + 5;
template <typename T>
struct Point {
  T x, y;
  Point() : x(0), y(0) {}
  Point(T _x, T _y) : x(_x), y(_y) {}
  friend istream &operator>>(std::istream &i, Point &p) {
    return i >> p.x >> p.y;
  }
  friend ostream &operator<<(std::ostream &o, const Point &p) {
    return o << "(" << p.x << ", " << p.y << ")";
  }
  Point unitPolar(T ang) {
    auto c = exp(ang * complex<T>(0, 1));
    return P(c.real(), c.imag());
  }
  T norm() const { return x * x + y * y; }
  double abs() const { return sqrt(norm()); }
  double ang() const { return atan2(y, x); }
  Point<T> conj() const { return {x, -y}; }
  Point &operator+=(const Point &o) {
    x += o.x;
    y += o.y;
    return *this;
  }
  Point &operator-=(const Point &o) {
    x -= o.x;
    y -= o.y;
    return *this;
  }
  Point &operator*=(const T &c) {
    x *= c;
    y *= c;
    return *this;
  }
  Point &operator/=(const T &c) {
    x /= c;
    y /= c;
    return *this;
  }
  friend Point operator+(const Point &a, const Point &b) {
    return Point(a) += b;
  }
  friend Point operator-(const Point &a, const Point &b) {
    return Point(a) -= b;
  }
  friend Point operator*(const Point &a, const T &c) { return Point(a) *= c; }
  friend Point operator*(const T &c, const Point &a) { return Point(a) *= c; }
  friend Point operator/(const Point &a, const T &c) { return Point(a) /= c; }
  bool operator==(const Point &o) const { return x == o.x && y == o.y; }
  bool operator!=(const Point &o) const { return x != o.x || y != o.y; }
  bool operator<(const Point &o) const {
    return (x != o.x) ? x < o.x : y < o.y;
  }
  bool operator>(const Point &o) const {
    return (x != o.x) ? x > o.x : y > o.y;
  }
  bool operator<=(const Point &o) const { return !(*this > o); }
  friend T dot(const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; }
  friend T cross(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
  }
  friend T cross(const Point &p, const Point &a, const Point &b) {
    return cross(a - p, b - p);
  }
  friend Point<T> operator*(const Point &a, const Point &b) {
    return {a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x};
  }
  friend Point<T> operator/(const Point &a, const Point &b) {
    return a * b.conj() / b.norm();
  }
  Point unit() const { return Point(*this) / abs(); }
  Point rotate(const double &ang) const {
    return *this * Point(cos(ang), sin(ang));
  }
  double dist(const Point &a) const { return (a - *this).abs(); }
  double dist(const Point &a, const Point &b) {
    return abs(cross(*this, a, b)) / a.dist(b);
  }
  Point reflect(const Point &a, const Point &b) const {
    return a + ((*this - a) / (b - a)).conj() * (b - a);
  }
  Point foot(const Point &a, const Point &b) const {
    return (*this + this->reflect(a, b)) / 2;
  }
  friend Point intersect(const Point &a, const Point &b, const Point &c,
                         const Point &d) {
    T u = cross(a, b, c), v = cross(a, b, d);
    return (d * u - c * v) / (u - v);
  }
  using polygon = std::vector<Point<T>>;
  friend polygon seg_intersect(Point a, Point b, Point c, Point d) {
    if (a > b) swap(a, b);
    if (c > d) swap(c, d);
    T a1 = cross(a, b, c), a2 = cross(a, b, d);
    if (a1 > a2) swap(a1, a2);
    if (!(a1 <= 0 && a2 >= 0)) return {};
    if (a1 == 0 && a2 == 0) {
      if (cross(a, c, d) != 0) return {};
      Point<T> x1 = max(a, c), x2 = min(b, d);
      if (x1 > x2) return {};
      if (x1 == x2) return {x1};
      return {x1, x2};
    }
    Point<T> z = intersect(a, b, c, d);
    if (a <= z && z <= b) return {z};
    return {};
  }
  friend std::ostream &operator<<(std::ostream &o, const polygon &poly) {
    o << "{";
    for (auto pt : poly) o << " " << pt;
    return o << " }";
  }
  enum class Classification { in, out, on };
  Classification classify(const polygon &p) const {
    bool ans = 0;
    for (int i = 0; i < int(p.size()); i++) {
      Point<T> a = p[i], b = p[(i + 1) % p.size()];
      if (cross(a, b, *this) == 0 && min(a, b) <= *this && *this <= max(a, b))
        return Classification::on;
      if (a.y > b.y) swap(a, b);
      if (a.y <= y && y < b.y && cross(*this, a, b) > 0) ans ^= 1;
    }
    return ans ? Classification::in : Classification::out;
  }
  friend polygon convex_hull(const std::vector<Point> &pts) {
    Point pivot = *min_element((pts).begin(), (pts).end());
    auto sorted = pts;
    sort((sorted).begin(), (sorted).end(),
         [&pivot](const Point &p, const Point &q) {
           T cp = cross(pivot, p, q);
           if (cp != 0) return cp > 0;
           return pivot.dist(p) < pivot.dist(q);
         });
    int j = 0;
    polygon res(pts.size());
    for (const Point &p : sorted) {
      while (j > 1 && cross(res[j - 2], res[j - 1], p) <= 0) j--;
      res[j++] = p;
    }
    res.erase(res.begin() + j, res.end());
    return res;
  }
  Point centroid(const vector<Point> &v) {
    Point cen(0, 0);
    T area = 0;
    for (int i = 0; i < int(((int)(v).size())); i++) {
      int j = (i + 1) % ((int)(v).size());
      T a = cross(v[i], v[j]);
      cen += a * (v[i] + v[j]);
      area += a;
    }
    return cen / area / (T)3;
  }
  friend T area(const polygon &p) {
    T a = 0;
    for (int i = 0; i < int(p.size()); i++)
      a += cross(p[i], p[i + 1 < ((int)(p).size()) ? i + 1 : 0]);
    return a;
  }
  template <typename U>
  static int sign(const U &v) {
    return (v > 0) - (v < 0);
  }
  friend int compare_by_angle(const Point &a, const Point &b) {
    return sign(cross(b, a));
  }
  friend int compare_by_angle(const Point &a, const Point &b,
                              const Point &origin) {
    return sign(cross(origin, b, a));
  }
  template <typename I>
  friend void sort_by_angle(I first, I last,
                            const Point<T> &origin = Point<T>{}) {
    first =
        partition(first, last, [&](const Point<T> &p) { return p == origin; });
    auto pivot =
        partition(first, last, [&](const Point<T> &p) { return p > origin; });
    auto compare = [&](const Point<T> &l, const Point<T> &r) {
      return compare_by_angle(l, r, origin) < 0;
    };
    sort(first, pivot, compare);
    sort(pivot, last, compare);
  }
  pair<Point, double> ccCenter(Point a, Point b, Point c) {
    b -= a;
    c -= a;
    Point res = b * c * (c.conj() - b.conj()) / (b * c.conj() - b.conj() * c);
    return {a + res, abs(res)};
  }
  pair<Point, double> mec(vector<Point> ps) {
    shuffle((ps).begin(), (ps).end(), mt19937(time(0)));
    Point o = ps[0];
    double r = 0, EPS = 1 + 1e-8;
    for (int i = 0; i < int(((int)(ps).size())); i++)
      if (abs(o - ps[i]) > r * EPS) {
        o = ps[i], r = 0;
        for (int j = 0; j < int(i); j++)
          if (abs(o - ps[j]) > r * EPS) {
            o = (ps[i] + ps[j]) / 2, r = abs(o - ps[i]);
            for (int k = 0; k < int(j); k++)
              if (abs(o - ps[k]) > r * EPS)
                tie(o, r) = ccCenter(ps[i], ps[j], ps[k]);
          }
      }
    return {o, r};
  }
};
using pt = Point<double>;
void solve() {
  int n, m;
  cin >> n >> m;
  vector<pt> a(n);
  cin >> a;
  if (area(a) < 0) reverse((a).begin(), (a).end());
  while (m--) {
    pt x, y;
    cin >> x >> y;
    ld ans = 0;
    vi sg;
    for (int k = 0; k < int(n); k++) {
      sg.push_back(pt::sign(cross(x, y, a[k])) >= 0);
    }
    for (int i = 0; i < int(n); i++) {
      int j = (i + 1) % n;
      if (sg[i] != sg[j]) {
        ans += pt::sign(cross(a[i] - a[j], y - x)) *
               dot(y - x, intersect(x, y, a[i], a[j]));
      }
      if (cross(x, y, a[i]) == 0 && cross(x, y, a[j]) == 0 &&
          dot(y - x, a[j] - a[i]) > 0) {
        ans += dot(y - x, a[j] - a[i]);
      }
    }
    cout << ans / (x - y).abs() << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  int t = 1, tc = 1;
  while (t--) {
    solve();
    tc++;
  }
  return 0;
}

```