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;
const long double eps = 1e-8;
const long double pi = acos(-1.0);
int sgn(long double x) {
  if (x < -eps) return -1;
  if (x > eps) return 1;
  return 0;
}
struct P;
struct LINE;
struct CIRCLE;
struct TRIANGLE;
struct POLYGON;
void kr(long double &x) {
  double t;
  scanf("%lf", &t);
  x = t;
}
void kr(long long &x) { scanf("%lld", &x); }
struct P {
  long double x, y;
  void read() {
    kr(x);
    kr(y);
  }
  P operator+(const P &t) const { return {x + t.x, y + t.y}; }
  P operator-(const P &t) const { return {x - t.x, y - t.y}; }
  P operator*(long double t) const { return {x * t, y * t}; }
  P operator/(long double t) const { return {x / t, y / t}; }
  long double operator*(const P &t) const { return x * t.y - y * t.x; }
  long double operator%(const P &t) const { return x * t.x + y * t.y; }
  bool operator<(const P &t) const { return x < t.x || x == t.x && y < t.y; }
  bool operator==(const P &t) const { return x == t.x && y == t.y; }
  long double ang() const { return atan2(y, x); }
  long double length() const { return sqrt(x * x + y * y); }
  P rotate(const P &t, long double sita) const {
    return {(x - t.x) * cos(sita) - (y - t.y) * sin(sita) + t.x,
            (x - t.x) * sin(sita) + (y - t.y) * cos(sita) + t.y};
  }
  long double btang(const P &t) const {
    return acos((*this % t) / length() / t.length());
  }
  P midvec(const P &t) const { return (*this) / length() + t / t.length(); }
};
struct LINE {
  P p1, p2;
  void read() {
    p1.read();
    p2.read();
  }
  LINE midLINE() {
    P midp = (p1 + p2) / 2;
    P v = p2 - p1;
    v = v.rotate({0, 0}, pi / 2);
    return {midp, midp + v};
  }
  bool have1(const P &p) const {
    return sgn((p - p1) * (p - p2)) == 0 && sgn((p - p1) % (p - p2)) <= 0;
  }
  bool have2(const P &p) const {
    return sgn((p - p1) * (p - p2)) == 0 && sgn((p - p1) % (p2 - p1)) >= 0;
  }
  bool have3(const P &p) const { return sgn((p - p1) * (p - p2)) == 0; }
  long double areawith(const P &p) const {
    return abs((p1 - p) * (p2 - p) / 2);
  }
  P vecfrom(const P &p) const {
    P v = (p2 - p1);
    v = v.rotate({0, 0}, pi / 2);
    long double s1 = (p1 - p) * (p2 - p);
    long double s2 = v * (p2 - p1);
    v = v * (s1 / s2);
    return v;
  }
  P footfrom(const P &p) const {
    P v = vecfrom(p);
    return p + v;
  }
  long double dis1from(const P &p) const {
    P foot = footfrom(p);
    if (have1(foot)) return (foot - p).length();
    return min((p1 - p).length(), (p2 - p).length());
  }
  long double dis2from(const P &p) const {
    P foot = footfrom(p);
    if (have2(foot)) return (foot - p).length();
    return (p1 - p).length();
  }
  long double dis3from(const P &p) const { return vecfrom(p).length(); }
  P symP(const P &p) const {
    P v = vecfrom(p);
    return p + v * 2;
  }
  bool isct11(const LINE &L) const {
    P a1 = p1, a2 = p2;
    P b1 = L.p1, b2 = L.p2;
    if (sgn(max(a1.x, a2.x) - min(b1.x, b2.x)) < 0 ||
        sgn(max(b1.x, b2.x) - min(a1.x, a2.x)) < 0 ||
        sgn(max(a1.y, a2.y) - min(b1.y, b2.y)) < 0 ||
        sgn(max(b1.y, b2.y) - min(a1.y, a2.y)) < 0)
      return 0;
    long double tmp1 = (a2 - a1) * (b1 - a1);
    long double tmp2 = (a2 - a1) * (b2 - a1);
    if (sgn(tmp1) < 0 && sgn(tmp2) < 0 || sgn(tmp1) > 0 && sgn(tmp2) > 0)
      return 0;
    tmp1 = (b2 - b1) * (a1 - b1);
    tmp2 = (b2 - b1) * (a2 - b1);
    if (sgn(tmp1) < 0 && sgn(tmp2) < 0 || sgn(tmp1) > 0 && sgn(tmp2) > 0)
      return 0;
    return 1;
  }
  bool isct21(const LINE &L) const {
    P v = p2 - p1;
    P a = p1;
    P b1 = L.p1, b2 = L.p2;
    long double tmp1 = v * (b1 - a);
    long double tmp2 = v * (b2 - a);
    if (sgn(tmp1) < 0 && sgn(tmp2) < 0 || sgn(tmp1) > 0 && sgn(tmp2) > 0)
      return 0;
    if (tmp1 > tmp2) swap(b1, b2);
    if (sgn((b1 - a) * (b2 - a)) > 0) return 1;
    if (sgn((b1 - a) * (b2 - a)) < 0) return 0;
    return L.have1(a) || have2(b1) || have2(b2);
  }
  bool isct31(const LINE &L) const {
    P v = p2 - p1;
    P a = p1;
    long double tmp1 = v * (L.p1 - a);
    long double tmp2 = v * (L.p2 - a);
    if (sgn(tmp1) < 0 && sgn(tmp2) < 0 || sgn(tmp1) > 0 && sgn(tmp2) > 0)
      return 0;
    return 1;
  }
  bool isct22(const LINE &L) const {
    if (have2(L.p1) || L.have2(p1)) return 1;
    P v = vecfrom(L.p1);
    if (sgn(v % (L.p2 - L.p1)) <= 0) return 0;
    v = L.vecfrom(p1);
    if (sgn(v % (p2 - p1)) <= 0) return 0;
    return 1;
  }
  bool isct32(const LINE &L) const {
    if (have3(L.p1)) return 1;
    P v = vecfrom(L.p1);
    if (sgn(v % (L.p2 - L.p1)) <= 0) return 0;
    return 1;
  }
  bool isct33(const LINE &L) const {
    if (have3(L.p1)) return 1;
    return sgn((p2 - p1) * (L.p2 - L.p1)) != 0;
  }
  long double dis33(const LINE &L) const {
    return (L.p1 - p1) * (L.p2 - p1) / ((p2 - p1) * (L.p2 - L.p1)) *
           (p2 - p1).length();
  }
  P isctPoint(const LINE &L) const {
    long double len = dis33(L);
    P v = p2 - p1;
    return p1 + v * (len / v.length());
  }
};
struct CIRCLE {
  P cent;
  long double r;
  void read() {
    cent.read();
    kr(r);
  }
  long double area() const { return pi * r * r; }
  bool have(const P &p) const { return sgn((p - cent).length() - r) <= 0; }
  P LeftcutPoint(const P &p) const {
    P v = p - cent;
    long double sita = acos(r / v.length());
    v = v.rotate({0, 0}, sita);
    v = v / v.length() * r;
    return cent + v;
  }
  P RightcutPoint(const P &p) const {
    P v = p - cent;
    long double sita = acos(r / v.length());
    v = v.rotate({0, 0}, -sita);
    v = v / v.length() * r;
    return cent + v;
  }
  bool isct3(const LINE &L) const { return sgn(L.dis3from(cent) - r) <= 0; }
  P vecto(const LINE &L) const {
    P v = L.p2 - L.p1;
    v = v.rotate({0, 0}, pi / 2);
    if (sgn(v % (L.p1 - cent)) < 0) v = v.rotate({0, 0}, pi);
    return v / v.length() * r;
  }
  P LeftisctPoint(const LINE &L) const {
    P v = vecto(L);
    long double d = L.dis3from(cent);
    long double sita = acos(d / r);
    return cent + v.rotate({0, 0}, sita);
  }
  P RightisctPoint(const LINE &L) const {
    P v = vecto(L);
    long double d = L.dis3from(cent);
    long double sita = acos(d / r);
    return cent + v.rotate({0, 0}, -sita);
  }
  bool separate(const CIRCLE &C) const {
    long double d = (cent - C.cent).length();
    return sgn(r + C.r - d) <= 0;
  }
  bool contain(const CIRCLE &C) const {
    if (sgn(r - C.r) < 0) return 0;
    long double d = (cent - C.cent).length();
    return sgn(d + C.r - r) <= 0;
  }
  long double isctarea(const CIRCLE &C) const {
    if (separate(C)) return 0;
    if (contain(C)) return C.area();
    if (C.contain(*this)) return area();
    long double d = (cent - C.cent).length();
    long double ang1 = acos((r * r + d * d - C.r * C.r) / 2 / r / d);
    long double ang2 = acos((C.r * C.r + d * d - r * r) / 2 / C.r / d);
    return ang1 * r * r + ang2 * C.r * C.r - r * r * sin(2 * ang1) / 2 -
           C.r * C.r * sin(2 * ang2) / 2;
  }
};
struct TRIANGLE {
  P p[3];
  long double area() const;
  P center1() const;
  P center2() const;
  P center3() const;
  bool have(const P &p) const;
  bool isctLINE1(const LINE &L) const;
  bool isctLINE2(const LINE &L) const;
  bool isctLINE3(const LINE &L) const;
  P FirstisctPoint(const LINE &L) const;
  P SecondisctPoint(const LINE &L) const;
  bool separate(const TRIANGLE &TRI) const;
  bool contain(const TRIANGLE &TRI) const;
  bool isct(const TRIANGLE &TRI) const;
  long double isctarea(const TRIANGLE &TRI) const;
  long double isctarea(const POLYGON &POL) const;
};
const int POLNUM = 1005;
struct PL {
  long double len;
  int v;
} stk[POLNUM];
int top;
bool cmplen(const PL &a, const PL &b) { return a.len < b.len; }
P cent;
bool cmpang(const P &p1, const P &p2) {
  int tmp = sgn((p1 - cent).ang() - (p2 - cent).ang());
  if (tmp != 0) return tmp < 0;
  return (p1 - cent).length() < (p2 - cent).length();
}
struct POLYGON {
  int n;
  P a[POLNUM];
  void read(int k) {
    for (int i = 1; i <= k; i++) a[i].read();
    n = k;
  }
  void ChangetoConvex() {
    for (int i = 2; i <= n; i++)
      if (a[i].x < a[1].x || a[i].x == a[1].x && a[i].y < a[1].y)
        swap(a[1], a[i]);
    cent = a[1];
    sort(a + 2, a + n + 1, cmpang);
    int top = 2;
    for (int i = 3; i <= n; i++) {
      while (top >= 2 && sgn((a[top] - a[top - 1]) * (a[i] - a[top])) <= 0)
        top--;
      a[++top] = a[i];
    }
    n = top;
  }
  long double Clength() const {
    long double ret = 0;
    for (int i = 2; i <= n; i++) ret += (a[i] - a[i - 1]).length();
    if (n > 2) ret += (a[1] - a[n]).length();
    return ret;
  }
  bool have(const P p) {
    int k, d1, d2, wn = 0;
    a[0] = a[n];
    for (int i = 1; i <= n; i++) {
      LINE L = {a[i - 1], a[i]};
      if (L.have1(p)) return 1;
      k = sgn((a[i] - a[i - 1]) * (p - a[i - 1]));
      d1 = sgn(a[i - 1].y - p.y);
      d2 = sgn(a[i].y - p.y);
      if (k > 0 && d1 <= 0 && d2 > 0) wn++;
      if (k < 0 && d2 <= 0 && d1 > 0) wn--;
    }
    return wn != 0;
  }
  long double cutlength(const LINE &L) {
    a[0] = a[n];
    top = 0;
    for (int i = 1; i <= n; i++) {
      LINE R = {a[i - 1], a[i]};
      long double s1 = sgn((L.p2 - L.p1) * (R.p1 - L.p1));
      long double s2 = sgn((L.p2 - L.p1) * (R.p2 - L.p1));
      if (s1 < 0 && s2 < 0 || s1 == 0 && s2 == 0 || s1 > 0 && s2 > 0) continue;
      if (s1 < s2)
        stk[++top] = {L.dis33(R), (s1 != 0 && s2 != 0 ? 2 : 1)};
      else
        stk[++top] = {L.dis33(R), (s1 != 0 && s2 != 0 ? -2 : -1)};
    }
    sort(stk + 1, stk + top + 1, cmplen);
    int cnt = 0;
    long double ret = 0;
    for (int i = 1; i <= top; i++) {
      if (cnt) ret += stk[i].len - stk[i - 1].len;
      cnt += stk[i].v;
    }
    return ret;
  }
  bool isct(const POLYGON &POL) const {
    for (int i = 2; i <= n; i++)
      for (int j = 2; j <= POL.n; j++) {
        LINE L1 = {a[i - 1], a[i]};
        LINE L2 = {POL.a[j - 1], POL.a[j]};
        if (L1.isct11(L2)) return 1;
      }
    return 0;
  }
  long double isctarea(const POLYGON &POL) const;
};
int main() {
  int n, m;
  cin >> n >> m;
  POLYGON poi;
  poi.read(n);
  for (int i = 1; i <= m; i++) {
    LINE L;
    L.read();
    printf("%.10f\n", (double)poi.cutlength(L));
  }
}