#include <bits/stdc++.h>
bool close(long double, long double);
long double orient;
struct vec {
  long double x;
  long double y;
  vec operator+(const vec &other) const {
    vec result;
    result.x = x + other.x;
    result.y = y + other.y;
    return result;
  }
  vec operator-(const vec &other) const {
    vec result;
    result.x = x - other.x;
    result.y = y - other.y;
    return result;
  }
  bool operator<(const vec &other) const {
    return (x < other.x) || (close(x, other.x) && y < other.y);
  }
  vec scale(long double scalar) const {
    vec result;
    result.x = scalar * x;
    result.y = scalar * y;
    return result;
  }
  void print() const { printf("(%Lf, %Lf)\n", x, y); }
  void read() { std::cin >> x >> y; }
};
long double cross(const vec &a, const vec &b) {
  return (a.y * b.x) - (a.x * b.y);
}
long double dist(const vec &a, const vec &b) {
  long double xx = a.x - b.x;
  long double yy = a.y - b.y;
  return sqrt(xx * xx + yy * yy);
}
struct segment {
  vec a;
  vec b;
};
struct matrix {
  long double i1;
  long double i2;
  long double i3;
  long double i4;
  long double det() { return (i1 * i4) - (i2 * i3); }
};
matrix build_matrix(long double i1, long double i2, long double i3,
                    long double i4) {
  matrix m;
  m.i1 = i1;
  m.i2 = i2;
  m.i3 = i3;
  m.i4 = i4;
  return m;
}
bool point_on_line(vec point, vec lpoint, vec ldir) {
  return cross(ldir, point - lpoint) == 0;
}
long double EPS = 0.0000000000001;
bool close(long double x, long double y) {
  long double diff = x - y;
  return diff > -EPS && diff < EPS;
}
bool between(long double x, long double a, long double b) {
  long double temp;
  if (a > b) {
    temp = a;
    a = b;
    b = temp;
  }
  bool result = (x > a || close(x, a)) && (x < b || close(x, b));
  return result;
}
std::pair<vec, bool> intersection(const vec &lpoint, const vec &ldir,
                                  const vec &prev, const vec &a) {
  matrix A;
  vec result;
  vec sdir;
  vec v;
  long double det;
  sdir = prev - a;
  v = a - lpoint;
  A = build_matrix(ldir.x, sdir.x, ldir.y, sdir.y);
  det = A.det();
  if (det == 0) {
    return std::make_pair(result, false);
  }
  long double t = (1 / det) * (A.i4 * v.x - A.i2 * v.y);
  result = lpoint + ldir.scale(t);
  if (between(result.x, prev.x, a.x) && between(result.y, prev.y, a.y))
    return std::make_pair(result, true);
  else {
    return std::make_pair(result, false);
  }
}
long double sign(long double x) {
  if (x < 0) return -1;
  if (x > 0) return 1;
  return 0;
}
bool is_convex(const vec &prev, const vec &cur, const vec &nex) {
  return sign(orient) == sign(cross(cur - prev, nex - cur));
}
vec vertices[1000];
vec inters[1000];
int main() {
  int n, m;
  vec vertex;
  int minidx;
  std::cin >> n >> m;
  vertex.read();
  vertices[0] = vertex;
  minidx = 0;
  for (int i = 1; i < n; i++) {
    vertex.read();
    vertices[i] = vertex;
    if (vertex < vertices[minidx]) {
      minidx = i;
    }
  }
  vec a, b;
  a = vertices[minidx] - vertices[(minidx - 1 + n) % n];
  b = vertices[(minidx + 1) % n] - vertices[minidx];
  orient = cross(a, b);
  for (int i = 0; i < m; i++) {
    int idx = 0;
    vec lpoint, lpoint2, ldir;
    lpoint.read();
    lpoint2.read();
    ldir = lpoint2 - lpoint;
    for (int j = 0; j < n; j++) {
      vec prev, cur, nex;
      prev = vertices[(j - 1 + n) % n];
      cur = vertices[j];
      nex = vertices[(j + 1) % n];
      bool prev_on_line = point_on_line(prev, lpoint, ldir);
      bool cur_on_line = point_on_line(cur, lpoint, ldir);
      bool nex_on_line = point_on_line(nex, lpoint, ldir);
      if ((prev_on_line && cur_on_line) || (cur_on_line && nex_on_line)) {
        if (is_convex(prev, cur, nex)) {
          inters[idx++] = cur;
        }
      } else if (cur_on_line) {
        std::pair<vec, bool> p = intersection(lpoint, ldir, prev, nex);
        if (p.second == true) {
          inters[idx++] = cur;
        }
      } else if (!cur_on_line && !prev_on_line) {
        std::pair<vec, bool> p = intersection(lpoint, ldir, prev, cur);
        if (p.second == true) {
          inters[idx++] = p.first;
        }
      }
    }
    std::sort(inters, inters + idx);
    long double ans = 0;
    for (int j = 0; j < idx; j += 2) {
      ans += dist(inters[j], inters[j + 1]);
    }
    printf("%.20Lf\n", ans);
  }
}

### Prompt

Develop a solution in cpp 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>
bool close(long double, long double);
long double orient;
struct vec {
  long double x;
  long double y;
  vec operator+(const vec &other) const {
    vec result;
    result.x = x + other.x;
    result.y = y + other.y;
    return result;
  }
  vec operator-(const vec &other) const {
    vec result;
    result.x = x - other.x;
    result.y = y - other.y;
    return result;
  }
  bool operator<(const vec &other) const {
    return (x < other.x) || (close(x, other.x) && y < other.y);
  }
  vec scale(long double scalar) const {
    vec result;
    result.x = scalar * x;
    result.y = scalar * y;
    return result;
  }
  void print() const { printf("(%Lf, %Lf)\n", x, y); }
  void read() { std::cin >> x >> y; }
};
long double cross(const vec &a, const vec &b) {
  return (a.y * b.x) - (a.x * b.y);
}
long double dist(const vec &a, const vec &b) {
  long double xx = a.x - b.x;
  long double yy = a.y - b.y;
  return sqrt(xx * xx + yy * yy);
}
struct segment {
  vec a;
  vec b;
};
struct matrix {
  long double i1;
  long double i2;
  long double i3;
  long double i4;
  long double det() { return (i1 * i4) - (i2 * i3); }
};
matrix build_matrix(long double i1, long double i2, long double i3,
                    long double i4) {
  matrix m;
  m.i1 = i1;
  m.i2 = i2;
  m.i3 = i3;
  m.i4 = i4;
  return m;
}
bool point_on_line(vec point, vec lpoint, vec ldir) {
  return cross(ldir, point - lpoint) == 0;
}
long double EPS = 0.0000000000001;
bool close(long double x, long double y) {
  long double diff = x - y;
  return diff > -EPS && diff < EPS;
}
bool between(long double x, long double a, long double b) {
  long double temp;
  if (a > b) {
    temp = a;
    a = b;
    b = temp;
  }
  bool result = (x > a || close(x, a)) && (x < b || close(x, b));
  return result;
}
std::pair<vec, bool> intersection(const vec &lpoint, const vec &ldir,
                                  const vec &prev, const vec &a) {
  matrix A;
  vec result;
  vec sdir;
  vec v;
  long double det;
  sdir = prev - a;
  v = a - lpoint;
  A = build_matrix(ldir.x, sdir.x, ldir.y, sdir.y);
  det = A.det();
  if (det == 0) {
    return std::make_pair(result, false);
  }
  long double t = (1 / det) * (A.i4 * v.x - A.i2 * v.y);
  result = lpoint + ldir.scale(t);
  if (between(result.x, prev.x, a.x) && between(result.y, prev.y, a.y))
    return std::make_pair(result, true);
  else {
    return std::make_pair(result, false);
  }
}
long double sign(long double x) {
  if (x < 0) return -1;
  if (x > 0) return 1;
  return 0;
}
bool is_convex(const vec &prev, const vec &cur, const vec &nex) {
  return sign(orient) == sign(cross(cur - prev, nex - cur));
}
vec vertices[1000];
vec inters[1000];
int main() {
  int n, m;
  vec vertex;
  int minidx;
  std::cin >> n >> m;
  vertex.read();
  vertices[0] = vertex;
  minidx = 0;
  for (int i = 1; i < n; i++) {
    vertex.read();
    vertices[i] = vertex;
    if (vertex < vertices[minidx]) {
      minidx = i;
    }
  }
  vec a, b;
  a = vertices[minidx] - vertices[(minidx - 1 + n) % n];
  b = vertices[(minidx + 1) % n] - vertices[minidx];
  orient = cross(a, b);
  for (int i = 0; i < m; i++) {
    int idx = 0;
    vec lpoint, lpoint2, ldir;
    lpoint.read();
    lpoint2.read();
    ldir = lpoint2 - lpoint;
    for (int j = 0; j < n; j++) {
      vec prev, cur, nex;
      prev = vertices[(j - 1 + n) % n];
      cur = vertices[j];
      nex = vertices[(j + 1) % n];
      bool prev_on_line = point_on_line(prev, lpoint, ldir);
      bool cur_on_line = point_on_line(cur, lpoint, ldir);
      bool nex_on_line = point_on_line(nex, lpoint, ldir);
      if ((prev_on_line && cur_on_line) || (cur_on_line && nex_on_line)) {
        if (is_convex(prev, cur, nex)) {
          inters[idx++] = cur;
        }
      } else if (cur_on_line) {
        std::pair<vec, bool> p = intersection(lpoint, ldir, prev, nex);
        if (p.second == true) {
          inters[idx++] = cur;
        }
      } else if (!cur_on_line && !prev_on_line) {
        std::pair<vec, bool> p = intersection(lpoint, ldir, prev, cur);
        if (p.second == true) {
          inters[idx++] = p.first;
        }
      }
    }
    std::sort(inters, inters + idx);
    long double ans = 0;
    for (int j = 0; j < idx; j += 2) {
      ans += dist(inters[j], inters[j + 1]);
    }
    printf("%.20Lf\n", ans);
  }
}

```