#include <bits/stdc++.h>
using namespace std;
template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T>>;
const int INF = static_cast<int>(1e9);
const long long INF_LL = static_cast<long long>(4e18);
const double pi = acos(-1.0);
template <class T>
inline T& smin(T& x, const T& y) {
  return x > y ? x = y : x;
}
template <class T>
inline T& smax(T& x, const T& y) {
  return x < y ? x = y : x;
}
template <class T>
inline T sqr(const T& x) {
  return x * x;
}
template <class T>
inline int sgn(const T& x) {
  return (T(0) < x) - (x < T(0));
}
template <class T>
T gcd(T a, T b) {
  for (a = abs(a), b = abs(b); a && b; a >= b ? a %= b : b %= a)
    ;
  return a + b;
}
using uint = unsigned int;
const uint BUFFER_SIZE = 1 << 12;
const uint MAX_LENGTH = 1 << 7;
namespace Detail {
struct Width {
  uint value;
};
struct Fill {
  char value;
};
struct Base {
  uint value;
};
struct Precision {
  uint value;
};
struct Delimiter {
  const char* value;
};
}  // namespace Detail
Detail::Width setWidth(uint value = 0) { return {value}; }
Detail::Fill setFill(char value = ' ') { return {value}; }
Detail::Base setBase(uint value = 10) {
  assert(2 <= value && value <= 36);
  return {value};
}
Detail::Precision setPrecision(uint value = 9) {
  assert(value < MAX_LENGTH);
  return {value};
}
Detail::Delimiter setDelimiter(const char* value = " ") { return {value}; }
class InputDevice {
 protected:
  const char* head;
  const char* tail;
  InputDevice(const char* head, const char* tail)
      : head(head), tail(tail), base(setBase().value) {}
  InputDevice(InputDevice const&) = delete;
  InputDevice& operator=(InputDevice const&) = delete;
  virtual void fillInput() = 0;
  inline char nextChar() {
    if (__builtin_expect(head >= tail, false)) fillInput();
    return *head++;
  }
  template <class I>
  int readUnsignedIntGeneral(I& arg, char c) {
    I value = 0;
    int length = 0;
    for (;; ++length, c = nextChar()) {
      if (isDigit(c))
        c -= '0';
      else if (isUpper(c))
        c -= 'A' - 10;
      else if (isLower(c))
        c -= 'a' - 10;
      else
        c = base;
      if (c >= base) break;
      value = base * value + c;
    }
    arg = value;
    return --head, length;
  }
  template <class I>
  inline int readUnsignedInt(I& arg, char c) {
    if (__builtin_expect(base > 10, false))
      return readUnsignedIntGeneral(arg, c);
    I value = 0;
    int length = 0;
    for (; static_cast<unsigned char>(c - '0') < base; ++length, c = nextChar())
      value = base * value + c - '0';
    arg = value;
    return --head, length;
  }
  template <class I>
  inline bool readSignedInt(I& arg, char c) {
    bool negative = c == '-';
    if (negative) c = nextChar();
    typename make_unsigned<I>::type unsignedArg;
    if (readUnsignedInt(unsignedArg, c) == 0) return false;
    arg = negative ? ~static_cast<I>(unsignedArg - 1)
                   : static_cast<I>(unsignedArg);
    return true;
  }
  template <class F>
  bool readFloatingPoint(F& arg, char c) {
    bool negative = c == '-';
    if (negative) c = nextChar();
    unsigned long long integerPart;
    if (readUnsignedInt(integerPart, c) == 0) return false;
    arg = static_cast<F>(integerPart);
    if (nextChar() == '.') {
      unsigned long long fractionalPart = 0;
      int fractionalLength = readUnsignedInt(fractionalPart, nextChar());
      if (fractionalLength > 0) {
        unsigned long long basePower = 1;
        for (; fractionalLength; --fractionalLength) basePower *= base;
        arg += static_cast<F>(fractionalPart) / basePower;
      }
    } else
      --head;
    if (negative) arg = -arg;
    return true;
  }

 public:
  static inline bool isSpace(char c) {
    return static_cast<unsigned char>(c - '\t') < 5 || c == ' ';
  }
  static inline bool isDigit(char c) {
    return static_cast<unsigned char>(c - '0') < 10;
  }
  static inline bool isUpper(char c) {
    return static_cast<unsigned char>(c - 'A') < 26;
  }
  static inline bool isLower(char c) {
    return static_cast<unsigned char>(c - 'a') < 26;
  }
  static inline bool isOneOf(char c, const char* str) {
    return strchr(str, c) != nullptr;
  }
  uint base;
  void putBack() { --head; }
  inline bool readChar(char& arg) {
    if (__builtin_expect(head >= tail, false)) {
      fillInput();
      if (__builtin_expect(head >= tail, false)) return arg = '\0', false;
    }
    return arg = *head++, true;
  }
  template <class UnaryPredicate>
  inline char skipCharacters(UnaryPredicate isSkipped) {
    char c;
    do {
      c = nextChar();
    } while (isSkipped(c));
    return c;
  }
  inline char skipCharacters() { return skipCharacters(isSpace); }
  template <class UnaryPredicate>
  inline bool readString(char* arg, int limit, UnaryPredicate isTerminator) {
    skipCharacters(isTerminator);
    for (--head, --limit; head < tail; fillInput()) {
      ptrdiff_t chunkSize =
          find_if(head, min(tail, head + limit), isTerminator) - head;
      arg = copy_n(head, chunkSize, arg);
      head += chunkSize;
      limit -= chunkSize;
      if (chunkSize == 0 || head < tail) break;
    }
    return *arg = '\0', true;
  }
  template <class I>
  inline bool readUnsignedInt(I& arg) {
    return readUnsignedInt(arg, skipCharacters()) > 0;
  }
  template <class I>
  inline bool readSignedInt(I& arg) {
    return readSignedInt(arg, skipCharacters());
  }
  template <class F>
  inline bool readFloatingPoint(F& arg) {
    return readFloatingPoint(arg, skipCharacters());
  }
};
class InputFile : public InputDevice {
  FILE* file;
  bool lineBuffered;
  bool owner;
  char buffer[BUFFER_SIZE];
  void fillInput() override {
    head = buffer;
    *buffer = '\0';
    if (__builtin_expect(!lineBuffered, true)) {
      tail = head + fread(buffer, 1, BUFFER_SIZE, file);
    } else {
      tail = head;
      if (fgets(buffer, BUFFER_SIZE, file))
        while (*tail) ++tail;
    }
  }

 public:
  InputFile(FILE* file = stdin, bool lineBuffered = true,
            bool takeOwnership = false)
      : InputDevice(buffer, buffer),
        file(file),
        lineBuffered(lineBuffered),
        owner(takeOwnership) {}
  InputFile(const char* fileName)
      : InputFile(fopen(fileName, "r"), false, true) {}
  ~InputFile() {
    if (owner) fclose(file);
  }
};
class InputString : public InputDevice {
  void fillInput() override {
    while (*tail) ++tail;
  }

 public:
  InputString(const string& s) : InputDevice(s.data(), s.data() + s.size()) {}
  InputString(const char* s) : InputDevice(s, s + strlen(s)) {}
};
class OutputDevice {
 protected:
  char buffer[BUFFER_SIZE + MAX_LENGTH];
  char* output;
  char* end;
  bool separate;
  OutputDevice()
      : output(buffer),
        end(buffer + BUFFER_SIZE + MAX_LENGTH),
        separate(false),
        width(setWidth().value),
        fill(setFill().value),
        base(setBase().value),
        precision(setPrecision().value),
        delimiter(setDelimiter().value) {}
  OutputDevice(OutputDevice const&) = delete;
  OutputDevice& operator=(OutputDevice const&) = delete;
  virtual void writeToDevice(uint count) = 0;
  inline void flushMaybe() {
    if (__builtin_expect(output >= buffer + BUFFER_SIZE, false)) {
      writeToDevice(BUFFER_SIZE);
      output = copy(buffer + BUFFER_SIZE, output, buffer);
    }
  }
  template <class I>
  inline char* writeUnsignedInt(I arg, char* last) {
    if (__builtin_expect(arg == 0, false)) *--last = '0';
    if (__builtin_expect(base == 10, true)) {
      for (; arg; arg /= 10) *--last = '0' + arg % 10;
    } else
      for (; arg; arg /= base) {
        I digit = arg % base;
        *--last = digit < 10 ? '0' + digit : 'A' - 10 + digit;
      }
    return last;
  }
  template <class I>
  inline char* writeSignedInt(I arg, char* last) {
    auto unsignedArg = static_cast<typename make_unsigned<I>::type>(arg);
    if (arg < 0) {
      last = writeUnsignedInt(~unsignedArg + 1, last);
      *--last = '-';
      return last;
    }
    return writeUnsignedInt(unsignedArg, last);
  }
  template <class F>
  char* writeFloatingPoint(F arg, char* last) {
    bool negative = signbit(arg);
    if (negative) arg = -arg;
    if (isnan(arg))
      for (int i = 0; i < 3; ++i) *--last = i["NaN"];
    else if (isinf(arg))
      for (int i = 0; i < 3; ++i) *--last = i["fnI"];
    else {
      auto integerPart = static_cast<unsigned long long>(arg);
      arg -= integerPart;
      for (int i = 0; i < precision; ++i) arg *= base;
      auto fractionalPart = static_cast<unsigned long long>(arg);
      if ((arg - fractionalPart) * 2 >= static_cast<F>(1)) {
        if (precision == 0)
          ++integerPart;
        else
          ++fractionalPart;
      }
      if (precision > 0) {
        char* point = last - precision;
        last = writeUnsignedInt(fractionalPart, last);
        ::fill(point, last, '0');
        last = point;
        *--last = '.';
      }
      last = writeUnsignedInt(integerPart, last);
    }
    if (negative) *--last = '-';
    return last;
  }
  inline int writeT(char* first) {
    int delimiterLenght = separate ? writeDelimiter() : 0;
    separate = true;
    int charsWritten = static_cast<int>(end - first);
    if (__builtin_expect(charsWritten < width, false))
      charsWritten += writeFill(width - charsWritten);
    output = copy(first, end, output);
    flushMaybe();
    return delimiterLenght + charsWritten;
  }
  inline int writeFill(int count) {
    int result = count;
    if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
      if (count == 1)
        *output++ = fill;
      else
        output = fill_n(output, count, fill);
    } else
      for (uint chunkSize = static_cast<uint>(buffer + BUFFER_SIZE - output);;
           chunkSize = BUFFER_SIZE) {
        if (chunkSize > count) chunkSize = count;
        output = fill_n(output, chunkSize, fill);
        flushMaybe();
        if ((count -= chunkSize) == 0) break;
      }
    return result;
  }

 public:
  int width;
  char fill;
  uint base;
  uint precision;
  string delimiter;
  inline int writeChar(char arg) {
    separate = false;
    *output++ = arg;
    flushMaybe();
    return 1;
  }
  inline int writeString(const char* arg, int count, bool checkWidth = true) {
    separate = false;
    int result =
        count + (checkWidth && count < width ? writeFill(width - count) : 0);
    if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
      if (count == 1)
        *output++ = *arg;
      else
        output = copy_n(arg, count, output);
    } else
      for (int chunkSize = static_cast<int>(buffer + BUFFER_SIZE - output);;
           chunkSize = BUFFER_SIZE) {
        if (chunkSize > count) chunkSize = count;
        output = copy_n(arg, chunkSize, output);
        flushMaybe();
        if ((count -= chunkSize) == 0) break;
        arg += chunkSize;
      }
    return result;
  }
  inline int writeDelimiter() {
    return writeString(delimiter.c_str(), static_cast<int>(delimiter.size()),
                       false);
  }
  template <class I>
  inline int writeUnsignedInt(I arg) {
    return writeT(writeUnsignedInt(arg, end));
  }
  template <class I>
  inline int writeSignedInt(I arg) {
    return writeT(writeSignedInt(arg, end));
  }
  template <class F>
  inline int writeFloatingPoint(F arg) {
    return writeT(writeFloatingPoint(arg, end));
  }
  inline void flush() {
    writeToDevice(static_cast<uint>(output - buffer));
    output = buffer;
  }
  virtual ~OutputDevice(){};
};
class OutputFile : public OutputDevice {
  FILE* file;
  bool owner;
  void writeToDevice(uint count) override {
    fwrite(buffer, 1, count, file);
    fflush(file);
  }

 public:
  OutputFile(FILE* file = stdout, bool takeOwnership = false)
      : file(file), owner(takeOwnership) {}
  OutputFile(const char* fileName) : OutputFile(fopen(fileName, "w"), true) {}
  ~OutputFile() override {
    flush();
    if (owner) fclose(file);
  }
};
class OutputString : public OutputDevice {
  string& str;
  void writeToDevice(uint count) override { str.append(buffer, count); }

 public:
  OutputString(string& str) : OutputDevice(), str(str) {}
  ~OutputString() override { flush(); }
};
unique_ptr<InputFile> input;
unique_ptr<OutputFile> output;
inline int read(Detail::Base base) {
  input->base = base.value;
  return 0;
}
inline int read() { return 0; }
inline int read(char& arg) { return input->readChar(arg); }
template <class I>
inline typename enable_if<is_integral<I>::value && is_unsigned<I>::value,
                          int>::type
read(I& arg) {
  return input->readUnsignedInt(arg);
}
template <class I>
inline
    typename enable_if<is_integral<I>::value && is_signed<I>::value, int>::type
    read(I& arg) {
  return input->readSignedInt(arg);
}
template <class F>
inline typename enable_if<is_floating_point<F>::value, int>::type read(F& arg) {
  return input->readFloatingPoint(arg);
}
inline int read(const char& arg) {
  input->skipCharacters([arg](char c) { return arg != c; });
  return 0;
}
inline int read(const char* arg) {
  if (*arg)
    input->skipCharacters(
        [arg](char c) { return InputDevice::isOneOf(c, arg); });
  else
    input->skipCharacters();
  input->putBack();
  return 0;
}
inline int read(bool (*isSkipped)(char)) {
  input->skipCharacters(isSkipped);
  input->putBack();
  return 0;
}
template <class... Ts>
int read(char* arg, int limit, bool (*isTerminator)(char), Ts&&... args);
template <class... Ts>
int read(char* arg, int limit, const char* terminators, Ts&&... args);
template <class Iterator, class... Ts,
          typename = decltype(*std::declval<Iterator>())>
int read(Iterator first, Iterator last, Ts&&... args);
template <class Iterator, class... Ts,
          typename = decltype(*std::declval<Iterator>())>
int read(Iterator first, int count, Ts&&... args);
template <
    class T, class... Ts,
    typename = typename enable_if<!is_convertible<T, char*>::value, void>::type>
int read(T&& arg1, Ts&&... args);
inline int read(char* arg, int limit, const char* terminators = "") {
  if (!*terminators)
    return input->readString(arg, limit, InputDevice::isSpace);
  else
    return input->readString(arg, limit, [terminators](char c) {
      return InputDevice::isOneOf(c, terminators);
    });
}
template <class... Ts>
inline int read(char* first, char* last, Ts&&... args) {
  return read(first, static_cast<int>(last - first), forward<Ts>(args)...);
}
template <int N, class... Ts>
inline int read(char (&arg)[N], Ts&&... args) {
  return read(static_cast<char*>(arg), N, forward<Ts>(args)...);
}
template <class... Ts>
inline int read(char* arg, int limit, bool (*isTerminator)(char),
                Ts&&... args) {
  int argsRead = input->readString(arg, limit, isTerminator);
  return argsRead + read(forward<Ts>(args)...);
}
template <class... Ts>
inline int read(char* arg, int limit, const char* terminators, Ts&&... args) {
  int argsRead = read(arg, limit, terminators);
  return argsRead + read(forward<Ts>(args)...);
}
template <class T1, class T2>
inline int read(pair<T1, T2>& arg) {
  return read(arg.first) == 1 && read(arg.second) == 1 ? 1 : 0;
}
template <class T>
inline int read(vector<T>& arg) {
  uint n;
  if (read(n) == 0) return 0;
  arg.resize(n);
  return read(arg.begin(), arg.end());
}
template <class Iterator, class... Ts, typename>
int read(Iterator first, Iterator last, Ts&&... args) {
  int success = 1;
  for (; first != last; ++first) success &= read(*first);
  return success + read(forward<Ts>(args)...);
}
template <class Iterator, class... Ts, typename>
int read(Iterator first, int count, Ts&&... args) {
  return read(first, first + count, forward<Ts>(args)...);
}
template <class T, class... Ts, typename>
inline int read(T&& arg1, Ts&&... args) {
  int argsRead = read(forward<T>(arg1));
  return argsRead + read(forward<Ts>(args)...);
}
inline int write(Detail::Width width) {
  output->width = static_cast<int>(width.value);
  return 0;
}
inline int write(Detail::Fill fill) {
  output->fill = fill.value;
  return 0;
}
inline int write(Detail::Base base) {
  output->base = base.value;
  return 0;
}
inline int write(Detail::Precision precision) {
  output->precision = precision.value;
  return 0;
}
inline int write(Detail::Delimiter delimiter) {
  output->delimiter = delimiter.value;
  return 0;
}
inline int write() { return 0; }
inline int write(char arg) { return output->writeChar(arg); }
template <class I>
inline typename enable_if<is_integral<I>::value && is_unsigned<I>::value,
                          int>::type
write(I arg) {
  return output->writeUnsignedInt(arg);
}
template <class I>
inline
    typename enable_if<is_integral<I>::value && is_signed<I>::value, int>::type
    write(I arg) {
  return output->writeSignedInt(arg);
}
template <class F>
inline typename enable_if<is_floating_point<F>::value, int>::type write(F arg) {
  return output->writeFloatingPoint(arg);
}
inline int write(const char* arg) {
  return output->writeString(arg, static_cast<int>(strlen(arg)));
}
template <int N>
inline int write(char (&arg)[N]) {
  return output->writeString(arg, static_cast<int>(strlen(arg)));
}
inline int write(const string& arg) {
  return output->writeString(arg.c_str(), static_cast<int>(arg.size()));
}
template <class T1, class T2>
inline int write(const pair<T1, T2>& arg) {
  int charsWritten = write(arg.first);
  charsWritten += output->writeDelimiter();
  return charsWritten + write(arg.second);
}
template <
    class Iterator, class... Ts,
    typename = typename enable_if<!is_convertible<Iterator, const char*>::value,
                                  decltype(*std::declval<Iterator>())>::type>
int write(Iterator first, Iterator last, Ts&&... args);
template <
    class Iterator, class... Ts,
    typename = typename enable_if<!is_convertible<Iterator, const char*>::value,
                                  decltype(*std::declval<Iterator>())>::type>
int write(Iterator first, int count, Ts&&... args);
template <class T, class T2, class... Ts>
int write(T&& arg, T2&& arg2, Ts&&... args);
template <class Iterator, class... Ts, typename>
int write(Iterator first, Iterator last, Ts&&... args) {
  int charsWritten = 0;
  for (; first != last;
       charsWritten += ++first == last ? 0 : output->writeDelimiter())
    charsWritten += write(*first);
  return charsWritten + write(forward<Ts>(args)...);
}
template <class Iterator, class... Ts, typename>
int write(Iterator first, int count, Ts&&... args) {
  return write(first, first + count, forward<Ts>(args)...);
}
template <class T, class T2, class... Ts>
inline int write(T&& arg, T2&& arg2, Ts&&... args) {
  int charsWritten = write(forward<T>(arg));
  return charsWritten + write(forward<T2>(arg2), forward<Ts>(args)...);
}
template <class... Ts>
inline int writeln(Ts&&... args) {
  return write(forward<Ts>(args)..., '\n');
}
void flush() { output->flush(); }
template <class F>
struct Point {
  F x, y;
  Point() : x(0), y(0) {}
  Point(const F& x, const F& y) : x(x), y(y) {}
  void swap(Point& other) {
    using std::swap;
    swap(x, other.x);
    swap(y, other.y);
  }
  template <class F1>
  explicit operator Point<F1>() const {
    return Point<F1>(static_cast<F1>(x), static_cast<F1>(y));
  }
  template <class F1>
  Point& operator=(const Point<F1>& other) {
    x = other.x;
    y = other.y;
    return *this;
  }
  template <class F1>
  Point& operator+=(const Point<F1>& other) {
    x += other.x;
    y += other.y;
    return *this;
  }
  template <class F1>
  Point& operator-=(const Point<F1>& other) {
    x -= other.x;
    y -= other.y;
    return *this;
  }
  template <class F1>
  Point& operator*=(const F1& factor) {
    x *= factor;
    y *= factor;
    return *this;
  }
  template <class F1>
  Point& operator/=(const F1& factor) {
    x /= factor;
    y /= factor;
    return *this;
  }
};
template <class F>
int read(Point<F>& point) {
  return read(point.x, point.y) / 2;
}
template <class F>
int write(const Point<F>& point) {
  return write(point.x, point.y);
}
template <class F>
istream& operator>>(istream& is, Point<F>& point) {
  return is >> point.x >> point.y;
}
template <class F>
ostream& operator<<(ostream& os, const Point<F>& point) {
  return os << point.x << ' ' << point.y;
}
template <class F>
inline Point<F> makePoint(const F& x, const F& y) {
  return Point<F>(x, y);
}
template <class F>
void swap(Point<F>& lhs, Point<F>& rhs) {
  lhs.swap(rhs);
}
template <class F>
inline auto operator-(const Point<F>& point)
    -> decltype(makePoint(-point.x, -point.y)) {
  return makePoint(-point.x, -point.y);
}
template <class F1, class F2>
inline auto operator+(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(makePoint(lhs.x + rhs.x, lhs.y + rhs.y)) {
  return makePoint(lhs.x + rhs.x, lhs.y + rhs.y);
}
template <class F1, class F2>
inline auto operator-(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(makePoint(lhs.x - rhs.x, lhs.y - rhs.y)) {
  return makePoint(lhs.x - rhs.x, lhs.y - rhs.y);
}
template <class F1, class F2>
inline auto operator*(const F1& factor, const Point<F2>& rhs)
    -> decltype(makePoint(factor * rhs.x, factor* rhs.y)) {
  return makePoint(factor * rhs.x, factor * rhs.y);
}
template <class F1, class F2>
inline auto operator*(const Point<F1>& lhs, const F2& factor)
    -> decltype(makePoint(lhs.x * factor, lhs.y* factor)) {
  return makePoint(lhs.x * factor, lhs.y * factor);
}
template <class F1, class F2>
inline auto operator/(const Point<F1>& lhs, const F2& factor)
    -> decltype(makePoint(lhs.x / factor, lhs.y / factor)) {
  return makePoint(lhs.x / factor, lhs.y / factor);
}
template <class F1, class F2>
inline auto operator*(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.x * rhs.x + lhs.y * rhs.y) {
  return lhs.x * rhs.x + lhs.y * rhs.y;
}
template <class F1, class F2>
inline auto operator^(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.x * rhs.y - lhs.y * rhs.x) {
  return lhs.x * rhs.y - lhs.y * rhs.x;
}
template <class F1, class F2>
inline auto ccw(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(rhs ^ lhs) {
  return rhs ^ lhs;
}
template <class F1, class F2, class F3>
inline auto ccw(const Point<F1>& lhs, const Point<F2>& rhs,
                const Point<F3>& origin)
    -> decltype(ccw(lhs - origin, rhs - origin)) {
  return ccw(lhs - origin, rhs - origin);
}
template <class F1, class F2>
inline auto operator==(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.x == rhs.x && lhs.y == rhs.y) {
  return lhs.x == rhs.x && lhs.y == rhs.y;
}
template <class F1, class F2>
inline auto operator!=(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(!(lhs == rhs)) {
  return !(lhs == rhs);
}
template <class F1, class F2>
inline auto operator<(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.y < rhs.y || (lhs.y == rhs.y && lhs.x < rhs.x)) {
  return lhs.y < rhs.y || (lhs.y == rhs.y && lhs.x < rhs.x);
}
template <class F1, class F2>
inline auto operator>(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.y > rhs.y || (lhs.y == rhs.y && lhs.x > rhs.x)) {
  return lhs.y > rhs.y || (lhs.y == rhs.y && lhs.x > rhs.x);
}
template <class F1, class F2>
inline auto operator<=(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.y <= rhs.y || (lhs.y == rhs.y && lhs.x <= rhs.x)) {
  return lhs.y <= rhs.y || (lhs.y == rhs.y && lhs.x <= rhs.x);
}
template <class F1, class F2>
inline auto operator>=(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.y >= rhs.y || (lhs.y == rhs.y && lhs.x >= rhs.x)) {
  return lhs.y >= rhs.y || (lhs.y == rhs.y && lhs.x >= rhs.x);
}
template <class F>
inline auto angle(const Point<F>& point) -> decltype(atan2(point.y, point.x)) {
  return atan2(point.y, point.x);
}
template <class F1, class F2>
inline auto angle(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(atan2(lhs ^ rhs, lhs* rhs)) {
  return atan2(lhs ^ rhs, lhs * rhs);
}
template <class F1, class F2, class F3>
inline auto angle(const Point<F1>& lhs, const Point<F2>& rhs,
                  const Point<F3>& origin)
    -> decltype(angle(lhs - origin, rhs - origin)) {
  return angle(lhs - origin, rhs - origin);
}
template <class F1, class F2, class F3>
inline auto rotate(const Point<F1>& point, const F2& angleSin,
                   const F3& angleCos)
    -> decltype(makePoint(angleCos * point.x - angleSin * point.y,
                          angleSin* point.x + angleCos * point.y)) {
  return makePoint(angleCos * point.x - angleSin * point.y,
                   angleSin * point.x + angleCos * point.y);
}
template <class F1, class F2>
inline auto rotate(const Point<F1>& point, const F2& angle)
    -> decltype(rotate(point, sin(angle), cos(angle))) {
  return rotate(point, sin(angle), cos(angle));
}
template <class F1, class F2, class F3>
inline auto rotate(const Point<F1>& point, const F2& angle,
                   const Point<F3>& origin)
    -> decltype(origin + rotate(point - origin, angle)) {
  return origin + rotate(point - origin, angle);
}
template <class F>
inline auto perp(const Point<F>& point)
    -> decltype(makePoint(-point.y, point.x)) {
  return makePoint(-point.y, point.x);
}
template <class F>
inline auto abs(const Point<F>& point) -> decltype(point * point) {
  return point * point;
}
template <class F>
inline auto norm(const Point<F>& point) -> decltype(sqrt(abs(point))) {
  return sqrt(abs(point));
}
template <class F1, class F2>
inline auto dist(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(norm(lhs - rhs)) {
  return norm(lhs - rhs);
}
template <class F1, class F2>
inline auto dist2(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(abs(lhs - rhs)) {
  return abs(lhs - rhs);
}
template <class F1, class F2>
inline auto bisector(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs * norm(rhs) + rhs * norm(lhs)) {
  return lhs * norm(rhs) + rhs * norm(lhs);
}
template <class F1, class F2>
using distF = decltype(sqrt(F1() + F2()));
template <class F>
struct Line {
  Point<F> a, ab;
  Line() : a(), ab() {}
  Line(const Point<F>& a, const Point<F>& b, bool twoPoints = true)
      : a(a), ab(twoPoints ? b - a : b) {}
  Line(const F& xa, const F& ya, const F& xb, const F& yb)
      : a(xa, ya), ab(xb - xa, yb - ya) {}
  void swap(Line& other) {
    using std::swap;
    swap(a, other.a);
    swap(ab, other.ab);
  }
  template <class F1>
  explicit operator Line<F1>() const {
    return Line<F1>(Point<F1>(a), Point<F1>(ab), false);
  }
  template <class F1>
  Line& operator=(const Line<F1>& other) {
    a = other.a;
    ab = other.ab;
    return *this;
  }
  Point<F> b() const { return a + ab; }
  operator bool() const { return ab != Point<F>(); }
};
template <class F>
int read(Line<F>& line) {
  int res = read(line.a, line.ab) / 2;
  return line.ab -= line.a, res;
}
template <class F>
inline Line<F> makeLine(const Point<F>& a, const Point<F>& b,
                        bool twoPoints = true) {
  return Line<F>(a, b, twoPoints);
}
template <class F>
void swap(Line<F>& lhs, Line<F>& rhs) {
  lhs.swap(rhs);
}
template <class F>
using Polygon = vector<Point<F>>;
inline int prev(int i, int n) { return i == 0 ? n - 1 : i - 1; }
inline int next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
template <class F>
bool orientation(const Polygon<F>& poly) {
  int n = static_cast<int>(poly.size());
  int i = static_cast<int>(min_element(begin(poly), end(poly)) - begin(poly));
  return ccw(poly[prev(i, n)], poly[next(i, n)], poly[i]) > 0;
}
template <class F1, class F2>
distF<F1, F2> intersectLinePolygon(const Line<F1>& line,
                                   const Polygon<F2>& poly) {
  using F = distF<F1, F2>;
  F res = F();
  int n = static_cast<int>(poly.size());
  auto vertexSgn = [&line, &poly](int i) {
    return sgn(line.ab ^ (poly[i] - line.a));
  };
  int sprev = vertexSgn(n - 1), si = vertexSgn(0), snext;
  for (int i = 0; i < n; ++i, sprev = si, si = snext) {
    snext = vertexSgn(next(i, n));
    if (si == 0) {
      F t = static_cast<F>((poly[i] - line.a) * line.ab) / abs(line.ab);
      if (sprev == 0) {
        if (snext != 0 && snext == sgn((poly[i] - poly[prev(i, n)]) * line.ab))
          res += snext * t;
      } else {
        if ((snext != 0 && snext != sprev) ||
            (snext == 0 &&
             sprev == sgn((poly[next(i, n)] - poly[i]) * line.ab)))
          res -= sprev * t;
      }
    } else if (snext == -si) {
      auto vect = poly[next(i, n)] - poly[i];
      res +=
          snext * static_cast<F>((poly[i] - line.a) ^ vect) / (line.ab ^ vect);
    }
  }
  return res * norm(line.ab);
}
inline int read(Point<long long>& point) {
  double x, y;
  read(x, y);
  point.x = static_cast<long long>(x * 100 + sgn(x) * 0.5);
  point.y = static_cast<long long>(y * 100 + sgn(y) * 0.5);
  return 1;
}
int main() {
  input.reset(new InputFile(stdin, false));
  output.reset(new OutputFile());
  int n, m;
  read(n, m);
  Polygon<long long> poly(n);
  read((poly).begin(), (poly).end());
  if (!orientation(poly)) reverse(poly.begin() + 1, poly.end());
  for (int i(0), b_(m); i < b_; ++i) {
    Line<long long> line;
    read(line);
    printf("%.9lf\n", intersectLinePolygon(line, poly) / 100);
  }
  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>
using namespace std;
template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T>>;
const int INF = static_cast<int>(1e9);
const long long INF_LL = static_cast<long long>(4e18);
const double pi = acos(-1.0);
template <class T>
inline T& smin(T& x, const T& y) {
  return x > y ? x = y : x;
}
template <class T>
inline T& smax(T& x, const T& y) {
  return x < y ? x = y : x;
}
template <class T>
inline T sqr(const T& x) {
  return x * x;
}
template <class T>
inline int sgn(const T& x) {
  return (T(0) < x) - (x < T(0));
}
template <class T>
T gcd(T a, T b) {
  for (a = abs(a), b = abs(b); a && b; a >= b ? a %= b : b %= a)
    ;
  return a + b;
}
using uint = unsigned int;
const uint BUFFER_SIZE = 1 << 12;
const uint MAX_LENGTH = 1 << 7;
namespace Detail {
struct Width {
  uint value;
};
struct Fill {
  char value;
};
struct Base {
  uint value;
};
struct Precision {
  uint value;
};
struct Delimiter {
  const char* value;
};
}  // namespace Detail
Detail::Width setWidth(uint value = 0) { return {value}; }
Detail::Fill setFill(char value = ' ') { return {value}; }
Detail::Base setBase(uint value = 10) {
  assert(2 <= value && value <= 36);
  return {value};
}
Detail::Precision setPrecision(uint value = 9) {
  assert(value < MAX_LENGTH);
  return {value};
}
Detail::Delimiter setDelimiter(const char* value = " ") { return {value}; }
class InputDevice {
 protected:
  const char* head;
  const char* tail;
  InputDevice(const char* head, const char* tail)
      : head(head), tail(tail), base(setBase().value) {}
  InputDevice(InputDevice const&) = delete;
  InputDevice& operator=(InputDevice const&) = delete;
  virtual void fillInput() = 0;
  inline char nextChar() {
    if (__builtin_expect(head >= tail, false)) fillInput();
    return *head++;
  }
  template <class I>
  int readUnsignedIntGeneral(I& arg, char c) {
    I value = 0;
    int length = 0;
    for (;; ++length, c = nextChar()) {
      if (isDigit(c))
        c -= '0';
      else if (isUpper(c))
        c -= 'A' - 10;
      else if (isLower(c))
        c -= 'a' - 10;
      else
        c = base;
      if (c >= base) break;
      value = base * value + c;
    }
    arg = value;
    return --head, length;
  }
  template <class I>
  inline int readUnsignedInt(I& arg, char c) {
    if (__builtin_expect(base > 10, false))
      return readUnsignedIntGeneral(arg, c);
    I value = 0;
    int length = 0;
    for (; static_cast<unsigned char>(c - '0') < base; ++length, c = nextChar())
      value = base * value + c - '0';
    arg = value;
    return --head, length;
  }
  template <class I>
  inline bool readSignedInt(I& arg, char c) {
    bool negative = c == '-';
    if (negative) c = nextChar();
    typename make_unsigned<I>::type unsignedArg;
    if (readUnsignedInt(unsignedArg, c) == 0) return false;
    arg = negative ? ~static_cast<I>(unsignedArg - 1)
                   : static_cast<I>(unsignedArg);
    return true;
  }
  template <class F>
  bool readFloatingPoint(F& arg, char c) {
    bool negative = c == '-';
    if (negative) c = nextChar();
    unsigned long long integerPart;
    if (readUnsignedInt(integerPart, c) == 0) return false;
    arg = static_cast<F>(integerPart);
    if (nextChar() == '.') {
      unsigned long long fractionalPart = 0;
      int fractionalLength = readUnsignedInt(fractionalPart, nextChar());
      if (fractionalLength > 0) {
        unsigned long long basePower = 1;
        for (; fractionalLength; --fractionalLength) basePower *= base;
        arg += static_cast<F>(fractionalPart) / basePower;
      }
    } else
      --head;
    if (negative) arg = -arg;
    return true;
  }

 public:
  static inline bool isSpace(char c) {
    return static_cast<unsigned char>(c - '\t') < 5 || c == ' ';
  }
  static inline bool isDigit(char c) {
    return static_cast<unsigned char>(c - '0') < 10;
  }
  static inline bool isUpper(char c) {
    return static_cast<unsigned char>(c - 'A') < 26;
  }
  static inline bool isLower(char c) {
    return static_cast<unsigned char>(c - 'a') < 26;
  }
  static inline bool isOneOf(char c, const char* str) {
    return strchr(str, c) != nullptr;
  }
  uint base;
  void putBack() { --head; }
  inline bool readChar(char& arg) {
    if (__builtin_expect(head >= tail, false)) {
      fillInput();
      if (__builtin_expect(head >= tail, false)) return arg = '\0', false;
    }
    return arg = *head++, true;
  }
  template <class UnaryPredicate>
  inline char skipCharacters(UnaryPredicate isSkipped) {
    char c;
    do {
      c = nextChar();
    } while (isSkipped(c));
    return c;
  }
  inline char skipCharacters() { return skipCharacters(isSpace); }
  template <class UnaryPredicate>
  inline bool readString(char* arg, int limit, UnaryPredicate isTerminator) {
    skipCharacters(isTerminator);
    for (--head, --limit; head < tail; fillInput()) {
      ptrdiff_t chunkSize =
          find_if(head, min(tail, head + limit), isTerminator) - head;
      arg = copy_n(head, chunkSize, arg);
      head += chunkSize;
      limit -= chunkSize;
      if (chunkSize == 0 || head < tail) break;
    }
    return *arg = '\0', true;
  }
  template <class I>
  inline bool readUnsignedInt(I& arg) {
    return readUnsignedInt(arg, skipCharacters()) > 0;
  }
  template <class I>
  inline bool readSignedInt(I& arg) {
    return readSignedInt(arg, skipCharacters());
  }
  template <class F>
  inline bool readFloatingPoint(F& arg) {
    return readFloatingPoint(arg, skipCharacters());
  }
};
class InputFile : public InputDevice {
  FILE* file;
  bool lineBuffered;
  bool owner;
  char buffer[BUFFER_SIZE];
  void fillInput() override {
    head = buffer;
    *buffer = '\0';
    if (__builtin_expect(!lineBuffered, true)) {
      tail = head + fread(buffer, 1, BUFFER_SIZE, file);
    } else {
      tail = head;
      if (fgets(buffer, BUFFER_SIZE, file))
        while (*tail) ++tail;
    }
  }

 public:
  InputFile(FILE* file = stdin, bool lineBuffered = true,
            bool takeOwnership = false)
      : InputDevice(buffer, buffer),
        file(file),
        lineBuffered(lineBuffered),
        owner(takeOwnership) {}
  InputFile(const char* fileName)
      : InputFile(fopen(fileName, "r"), false, true) {}
  ~InputFile() {
    if (owner) fclose(file);
  }
};
class InputString : public InputDevice {
  void fillInput() override {
    while (*tail) ++tail;
  }

 public:
  InputString(const string& s) : InputDevice(s.data(), s.data() + s.size()) {}
  InputString(const char* s) : InputDevice(s, s + strlen(s)) {}
};
class OutputDevice {
 protected:
  char buffer[BUFFER_SIZE + MAX_LENGTH];
  char* output;
  char* end;
  bool separate;
  OutputDevice()
      : output(buffer),
        end(buffer + BUFFER_SIZE + MAX_LENGTH),
        separate(false),
        width(setWidth().value),
        fill(setFill().value),
        base(setBase().value),
        precision(setPrecision().value),
        delimiter(setDelimiter().value) {}
  OutputDevice(OutputDevice const&) = delete;
  OutputDevice& operator=(OutputDevice const&) = delete;
  virtual void writeToDevice(uint count) = 0;
  inline void flushMaybe() {
    if (__builtin_expect(output >= buffer + BUFFER_SIZE, false)) {
      writeToDevice(BUFFER_SIZE);
      output = copy(buffer + BUFFER_SIZE, output, buffer);
    }
  }
  template <class I>
  inline char* writeUnsignedInt(I arg, char* last) {
    if (__builtin_expect(arg == 0, false)) *--last = '0';
    if (__builtin_expect(base == 10, true)) {
      for (; arg; arg /= 10) *--last = '0' + arg % 10;
    } else
      for (; arg; arg /= base) {
        I digit = arg % base;
        *--last = digit < 10 ? '0' + digit : 'A' - 10 + digit;
      }
    return last;
  }
  template <class I>
  inline char* writeSignedInt(I arg, char* last) {
    auto unsignedArg = static_cast<typename make_unsigned<I>::type>(arg);
    if (arg < 0) {
      last = writeUnsignedInt(~unsignedArg + 1, last);
      *--last = '-';
      return last;
    }
    return writeUnsignedInt(unsignedArg, last);
  }
  template <class F>
  char* writeFloatingPoint(F arg, char* last) {
    bool negative = signbit(arg);
    if (negative) arg = -arg;
    if (isnan(arg))
      for (int i = 0; i < 3; ++i) *--last = i["NaN"];
    else if (isinf(arg))
      for (int i = 0; i < 3; ++i) *--last = i["fnI"];
    else {
      auto integerPart = static_cast<unsigned long long>(arg);
      arg -= integerPart;
      for (int i = 0; i < precision; ++i) arg *= base;
      auto fractionalPart = static_cast<unsigned long long>(arg);
      if ((arg - fractionalPart) * 2 >= static_cast<F>(1)) {
        if (precision == 0)
          ++integerPart;
        else
          ++fractionalPart;
      }
      if (precision > 0) {
        char* point = last - precision;
        last = writeUnsignedInt(fractionalPart, last);
        ::fill(point, last, '0');
        last = point;
        *--last = '.';
      }
      last = writeUnsignedInt(integerPart, last);
    }
    if (negative) *--last = '-';
    return last;
  }
  inline int writeT(char* first) {
    int delimiterLenght = separate ? writeDelimiter() : 0;
    separate = true;
    int charsWritten = static_cast<int>(end - first);
    if (__builtin_expect(charsWritten < width, false))
      charsWritten += writeFill(width - charsWritten);
    output = copy(first, end, output);
    flushMaybe();
    return delimiterLenght + charsWritten;
  }
  inline int writeFill(int count) {
    int result = count;
    if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
      if (count == 1)
        *output++ = fill;
      else
        output = fill_n(output, count, fill);
    } else
      for (uint chunkSize = static_cast<uint>(buffer + BUFFER_SIZE - output);;
           chunkSize = BUFFER_SIZE) {
        if (chunkSize > count) chunkSize = count;
        output = fill_n(output, chunkSize, fill);
        flushMaybe();
        if ((count -= chunkSize) == 0) break;
      }
    return result;
  }

 public:
  int width;
  char fill;
  uint base;
  uint precision;
  string delimiter;
  inline int writeChar(char arg) {
    separate = false;
    *output++ = arg;
    flushMaybe();
    return 1;
  }
  inline int writeString(const char* arg, int count, bool checkWidth = true) {
    separate = false;
    int result =
        count + (checkWidth && count < width ? writeFill(width - count) : 0);
    if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
      if (count == 1)
        *output++ = *arg;
      else
        output = copy_n(arg, count, output);
    } else
      for (int chunkSize = static_cast<int>(buffer + BUFFER_SIZE - output);;
           chunkSize = BUFFER_SIZE) {
        if (chunkSize > count) chunkSize = count;
        output = copy_n(arg, chunkSize, output);
        flushMaybe();
        if ((count -= chunkSize) == 0) break;
        arg += chunkSize;
      }
    return result;
  }
  inline int writeDelimiter() {
    return writeString(delimiter.c_str(), static_cast<int>(delimiter.size()),
                       false);
  }
  template <class I>
  inline int writeUnsignedInt(I arg) {
    return writeT(writeUnsignedInt(arg, end));
  }
  template <class I>
  inline int writeSignedInt(I arg) {
    return writeT(writeSignedInt(arg, end));
  }
  template <class F>
  inline int writeFloatingPoint(F arg) {
    return writeT(writeFloatingPoint(arg, end));
  }
  inline void flush() {
    writeToDevice(static_cast<uint>(output - buffer));
    output = buffer;
  }
  virtual ~OutputDevice(){};
};
class OutputFile : public OutputDevice {
  FILE* file;
  bool owner;
  void writeToDevice(uint count) override {
    fwrite(buffer, 1, count, file);
    fflush(file);
  }

 public:
  OutputFile(FILE* file = stdout, bool takeOwnership = false)
      : file(file), owner(takeOwnership) {}
  OutputFile(const char* fileName) : OutputFile(fopen(fileName, "w"), true) {}
  ~OutputFile() override {
    flush();
    if (owner) fclose(file);
  }
};
class OutputString : public OutputDevice {
  string& str;
  void writeToDevice(uint count) override { str.append(buffer, count); }

 public:
  OutputString(string& str) : OutputDevice(), str(str) {}
  ~OutputString() override { flush(); }
};
unique_ptr<InputFile> input;
unique_ptr<OutputFile> output;
inline int read(Detail::Base base) {
  input->base = base.value;
  return 0;
}
inline int read() { return 0; }
inline int read(char& arg) { return input->readChar(arg); }
template <class I>
inline typename enable_if<is_integral<I>::value && is_unsigned<I>::value,
                          int>::type
read(I& arg) {
  return input->readUnsignedInt(arg);
}
template <class I>
inline
    typename enable_if<is_integral<I>::value && is_signed<I>::value, int>::type
    read(I& arg) {
  return input->readSignedInt(arg);
}
template <class F>
inline typename enable_if<is_floating_point<F>::value, int>::type read(F& arg) {
  return input->readFloatingPoint(arg);
}
inline int read(const char& arg) {
  input->skipCharacters([arg](char c) { return arg != c; });
  return 0;
}
inline int read(const char* arg) {
  if (*arg)
    input->skipCharacters(
        [arg](char c) { return InputDevice::isOneOf(c, arg); });
  else
    input->skipCharacters();
  input->putBack();
  return 0;
}
inline int read(bool (*isSkipped)(char)) {
  input->skipCharacters(isSkipped);
  input->putBack();
  return 0;
}
template <class... Ts>
int read(char* arg, int limit, bool (*isTerminator)(char), Ts&&... args);
template <class... Ts>
int read(char* arg, int limit, const char* terminators, Ts&&... args);
template <class Iterator, class... Ts,
          typename = decltype(*std::declval<Iterator>())>
int read(Iterator first, Iterator last, Ts&&... args);
template <class Iterator, class... Ts,
          typename = decltype(*std::declval<Iterator>())>
int read(Iterator first, int count, Ts&&... args);
template <
    class T, class... Ts,
    typename = typename enable_if<!is_convertible<T, char*>::value, void>::type>
int read(T&& arg1, Ts&&... args);
inline int read(char* arg, int limit, const char* terminators = "") {
  if (!*terminators)
    return input->readString(arg, limit, InputDevice::isSpace);
  else
    return input->readString(arg, limit, [terminators](char c) {
      return InputDevice::isOneOf(c, terminators);
    });
}
template <class... Ts>
inline int read(char* first, char* last, Ts&&... args) {
  return read(first, static_cast<int>(last - first), forward<Ts>(args)...);
}
template <int N, class... Ts>
inline int read(char (&arg)[N], Ts&&... args) {
  return read(static_cast<char*>(arg), N, forward<Ts>(args)...);
}
template <class... Ts>
inline int read(char* arg, int limit, bool (*isTerminator)(char),
                Ts&&... args) {
  int argsRead = input->readString(arg, limit, isTerminator);
  return argsRead + read(forward<Ts>(args)...);
}
template <class... Ts>
inline int read(char* arg, int limit, const char* terminators, Ts&&... args) {
  int argsRead = read(arg, limit, terminators);
  return argsRead + read(forward<Ts>(args)...);
}
template <class T1, class T2>
inline int read(pair<T1, T2>& arg) {
  return read(arg.first) == 1 && read(arg.second) == 1 ? 1 : 0;
}
template <class T>
inline int read(vector<T>& arg) {
  uint n;
  if (read(n) == 0) return 0;
  arg.resize(n);
  return read(arg.begin(), arg.end());
}
template <class Iterator, class... Ts, typename>
int read(Iterator first, Iterator last, Ts&&... args) {
  int success = 1;
  for (; first != last; ++first) success &= read(*first);
  return success + read(forward<Ts>(args)...);
}
template <class Iterator, class... Ts, typename>
int read(Iterator first, int count, Ts&&... args) {
  return read(first, first + count, forward<Ts>(args)...);
}
template <class T, class... Ts, typename>
inline int read(T&& arg1, Ts&&... args) {
  int argsRead = read(forward<T>(arg1));
  return argsRead + read(forward<Ts>(args)...);
}
inline int write(Detail::Width width) {
  output->width = static_cast<int>(width.value);
  return 0;
}
inline int write(Detail::Fill fill) {
  output->fill = fill.value;
  return 0;
}
inline int write(Detail::Base base) {
  output->base = base.value;
  return 0;
}
inline int write(Detail::Precision precision) {
  output->precision = precision.value;
  return 0;
}
inline int write(Detail::Delimiter delimiter) {
  output->delimiter = delimiter.value;
  return 0;
}
inline int write() { return 0; }
inline int write(char arg) { return output->writeChar(arg); }
template <class I>
inline typename enable_if<is_integral<I>::value && is_unsigned<I>::value,
                          int>::type
write(I arg) {
  return output->writeUnsignedInt(arg);
}
template <class I>
inline
    typename enable_if<is_integral<I>::value && is_signed<I>::value, int>::type
    write(I arg) {
  return output->writeSignedInt(arg);
}
template <class F>
inline typename enable_if<is_floating_point<F>::value, int>::type write(F arg) {
  return output->writeFloatingPoint(arg);
}
inline int write(const char* arg) {
  return output->writeString(arg, static_cast<int>(strlen(arg)));
}
template <int N>
inline int write(char (&arg)[N]) {
  return output->writeString(arg, static_cast<int>(strlen(arg)));
}
inline int write(const string& arg) {
  return output->writeString(arg.c_str(), static_cast<int>(arg.size()));
}
template <class T1, class T2>
inline int write(const pair<T1, T2>& arg) {
  int charsWritten = write(arg.first);
  charsWritten += output->writeDelimiter();
  return charsWritten + write(arg.second);
}
template <
    class Iterator, class... Ts,
    typename = typename enable_if<!is_convertible<Iterator, const char*>::value,
                                  decltype(*std::declval<Iterator>())>::type>
int write(Iterator first, Iterator last, Ts&&... args);
template <
    class Iterator, class... Ts,
    typename = typename enable_if<!is_convertible<Iterator, const char*>::value,
                                  decltype(*std::declval<Iterator>())>::type>
int write(Iterator first, int count, Ts&&... args);
template <class T, class T2, class... Ts>
int write(T&& arg, T2&& arg2, Ts&&... args);
template <class Iterator, class... Ts, typename>
int write(Iterator first, Iterator last, Ts&&... args) {
  int charsWritten = 0;
  for (; first != last;
       charsWritten += ++first == last ? 0 : output->writeDelimiter())
    charsWritten += write(*first);
  return charsWritten + write(forward<Ts>(args)...);
}
template <class Iterator, class... Ts, typename>
int write(Iterator first, int count, Ts&&... args) {
  return write(first, first + count, forward<Ts>(args)...);
}
template <class T, class T2, class... Ts>
inline int write(T&& arg, T2&& arg2, Ts&&... args) {
  int charsWritten = write(forward<T>(arg));
  return charsWritten + write(forward<T2>(arg2), forward<Ts>(args)...);
}
template <class... Ts>
inline int writeln(Ts&&... args) {
  return write(forward<Ts>(args)..., '\n');
}
void flush() { output->flush(); }
template <class F>
struct Point {
  F x, y;
  Point() : x(0), y(0) {}
  Point(const F& x, const F& y) : x(x), y(y) {}
  void swap(Point& other) {
    using std::swap;
    swap(x, other.x);
    swap(y, other.y);
  }
  template <class F1>
  explicit operator Point<F1>() const {
    return Point<F1>(static_cast<F1>(x), static_cast<F1>(y));
  }
  template <class F1>
  Point& operator=(const Point<F1>& other) {
    x = other.x;
    y = other.y;
    return *this;
  }
  template <class F1>
  Point& operator+=(const Point<F1>& other) {
    x += other.x;
    y += other.y;
    return *this;
  }
  template <class F1>
  Point& operator-=(const Point<F1>& other) {
    x -= other.x;
    y -= other.y;
    return *this;
  }
  template <class F1>
  Point& operator*=(const F1& factor) {
    x *= factor;
    y *= factor;
    return *this;
  }
  template <class F1>
  Point& operator/=(const F1& factor) {
    x /= factor;
    y /= factor;
    return *this;
  }
};
template <class F>
int read(Point<F>& point) {
  return read(point.x, point.y) / 2;
}
template <class F>
int write(const Point<F>& point) {
  return write(point.x, point.y);
}
template <class F>
istream& operator>>(istream& is, Point<F>& point) {
  return is >> point.x >> point.y;
}
template <class F>
ostream& operator<<(ostream& os, const Point<F>& point) {
  return os << point.x << ' ' << point.y;
}
template <class F>
inline Point<F> makePoint(const F& x, const F& y) {
  return Point<F>(x, y);
}
template <class F>
void swap(Point<F>& lhs, Point<F>& rhs) {
  lhs.swap(rhs);
}
template <class F>
inline auto operator-(const Point<F>& point)
    -> decltype(makePoint(-point.x, -point.y)) {
  return makePoint(-point.x, -point.y);
}
template <class F1, class F2>
inline auto operator+(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(makePoint(lhs.x + rhs.x, lhs.y + rhs.y)) {
  return makePoint(lhs.x + rhs.x, lhs.y + rhs.y);
}
template <class F1, class F2>
inline auto operator-(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(makePoint(lhs.x - rhs.x, lhs.y - rhs.y)) {
  return makePoint(lhs.x - rhs.x, lhs.y - rhs.y);
}
template <class F1, class F2>
inline auto operator*(const F1& factor, const Point<F2>& rhs)
    -> decltype(makePoint(factor * rhs.x, factor* rhs.y)) {
  return makePoint(factor * rhs.x, factor * rhs.y);
}
template <class F1, class F2>
inline auto operator*(const Point<F1>& lhs, const F2& factor)
    -> decltype(makePoint(lhs.x * factor, lhs.y* factor)) {
  return makePoint(lhs.x * factor, lhs.y * factor);
}
template <class F1, class F2>
inline auto operator/(const Point<F1>& lhs, const F2& factor)
    -> decltype(makePoint(lhs.x / factor, lhs.y / factor)) {
  return makePoint(lhs.x / factor, lhs.y / factor);
}
template <class F1, class F2>
inline auto operator*(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.x * rhs.x + lhs.y * rhs.y) {
  return lhs.x * rhs.x + lhs.y * rhs.y;
}
template <class F1, class F2>
inline auto operator^(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.x * rhs.y - lhs.y * rhs.x) {
  return lhs.x * rhs.y - lhs.y * rhs.x;
}
template <class F1, class F2>
inline auto ccw(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(rhs ^ lhs) {
  return rhs ^ lhs;
}
template <class F1, class F2, class F3>
inline auto ccw(const Point<F1>& lhs, const Point<F2>& rhs,
                const Point<F3>& origin)
    -> decltype(ccw(lhs - origin, rhs - origin)) {
  return ccw(lhs - origin, rhs - origin);
}
template <class F1, class F2>
inline auto operator==(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.x == rhs.x && lhs.y == rhs.y) {
  return lhs.x == rhs.x && lhs.y == rhs.y;
}
template <class F1, class F2>
inline auto operator!=(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(!(lhs == rhs)) {
  return !(lhs == rhs);
}
template <class F1, class F2>
inline auto operator<(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.y < rhs.y || (lhs.y == rhs.y && lhs.x < rhs.x)) {
  return lhs.y < rhs.y || (lhs.y == rhs.y && lhs.x < rhs.x);
}
template <class F1, class F2>
inline auto operator>(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.y > rhs.y || (lhs.y == rhs.y && lhs.x > rhs.x)) {
  return lhs.y > rhs.y || (lhs.y == rhs.y && lhs.x > rhs.x);
}
template <class F1, class F2>
inline auto operator<=(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.y <= rhs.y || (lhs.y == rhs.y && lhs.x <= rhs.x)) {
  return lhs.y <= rhs.y || (lhs.y == rhs.y && lhs.x <= rhs.x);
}
template <class F1, class F2>
inline auto operator>=(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs.y >= rhs.y || (lhs.y == rhs.y && lhs.x >= rhs.x)) {
  return lhs.y >= rhs.y || (lhs.y == rhs.y && lhs.x >= rhs.x);
}
template <class F>
inline auto angle(const Point<F>& point) -> decltype(atan2(point.y, point.x)) {
  return atan2(point.y, point.x);
}
template <class F1, class F2>
inline auto angle(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(atan2(lhs ^ rhs, lhs* rhs)) {
  return atan2(lhs ^ rhs, lhs * rhs);
}
template <class F1, class F2, class F3>
inline auto angle(const Point<F1>& lhs, const Point<F2>& rhs,
                  const Point<F3>& origin)
    -> decltype(angle(lhs - origin, rhs - origin)) {
  return angle(lhs - origin, rhs - origin);
}
template <class F1, class F2, class F3>
inline auto rotate(const Point<F1>& point, const F2& angleSin,
                   const F3& angleCos)
    -> decltype(makePoint(angleCos * point.x - angleSin * point.y,
                          angleSin* point.x + angleCos * point.y)) {
  return makePoint(angleCos * point.x - angleSin * point.y,
                   angleSin * point.x + angleCos * point.y);
}
template <class F1, class F2>
inline auto rotate(const Point<F1>& point, const F2& angle)
    -> decltype(rotate(point, sin(angle), cos(angle))) {
  return rotate(point, sin(angle), cos(angle));
}
template <class F1, class F2, class F3>
inline auto rotate(const Point<F1>& point, const F2& angle,
                   const Point<F3>& origin)
    -> decltype(origin + rotate(point - origin, angle)) {
  return origin + rotate(point - origin, angle);
}
template <class F>
inline auto perp(const Point<F>& point)
    -> decltype(makePoint(-point.y, point.x)) {
  return makePoint(-point.y, point.x);
}
template <class F>
inline auto abs(const Point<F>& point) -> decltype(point * point) {
  return point * point;
}
template <class F>
inline auto norm(const Point<F>& point) -> decltype(sqrt(abs(point))) {
  return sqrt(abs(point));
}
template <class F1, class F2>
inline auto dist(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(norm(lhs - rhs)) {
  return norm(lhs - rhs);
}
template <class F1, class F2>
inline auto dist2(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(abs(lhs - rhs)) {
  return abs(lhs - rhs);
}
template <class F1, class F2>
inline auto bisector(const Point<F1>& lhs, const Point<F2>& rhs)
    -> decltype(lhs * norm(rhs) + rhs * norm(lhs)) {
  return lhs * norm(rhs) + rhs * norm(lhs);
}
template <class F1, class F2>
using distF = decltype(sqrt(F1() + F2()));
template <class F>
struct Line {
  Point<F> a, ab;
  Line() : a(), ab() {}
  Line(const Point<F>& a, const Point<F>& b, bool twoPoints = true)
      : a(a), ab(twoPoints ? b - a : b) {}
  Line(const F& xa, const F& ya, const F& xb, const F& yb)
      : a(xa, ya), ab(xb - xa, yb - ya) {}
  void swap(Line& other) {
    using std::swap;
    swap(a, other.a);
    swap(ab, other.ab);
  }
  template <class F1>
  explicit operator Line<F1>() const {
    return Line<F1>(Point<F1>(a), Point<F1>(ab), false);
  }
  template <class F1>
  Line& operator=(const Line<F1>& other) {
    a = other.a;
    ab = other.ab;
    return *this;
  }
  Point<F> b() const { return a + ab; }
  operator bool() const { return ab != Point<F>(); }
};
template <class F>
int read(Line<F>& line) {
  int res = read(line.a, line.ab) / 2;
  return line.ab -= line.a, res;
}
template <class F>
inline Line<F> makeLine(const Point<F>& a, const Point<F>& b,
                        bool twoPoints = true) {
  return Line<F>(a, b, twoPoints);
}
template <class F>
void swap(Line<F>& lhs, Line<F>& rhs) {
  lhs.swap(rhs);
}
template <class F>
using Polygon = vector<Point<F>>;
inline int prev(int i, int n) { return i == 0 ? n - 1 : i - 1; }
inline int next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
template <class F>
bool orientation(const Polygon<F>& poly) {
  int n = static_cast<int>(poly.size());
  int i = static_cast<int>(min_element(begin(poly), end(poly)) - begin(poly));
  return ccw(poly[prev(i, n)], poly[next(i, n)], poly[i]) > 0;
}
template <class F1, class F2>
distF<F1, F2> intersectLinePolygon(const Line<F1>& line,
                                   const Polygon<F2>& poly) {
  using F = distF<F1, F2>;
  F res = F();
  int n = static_cast<int>(poly.size());
  auto vertexSgn = [&line, &poly](int i) {
    return sgn(line.ab ^ (poly[i] - line.a));
  };
  int sprev = vertexSgn(n - 1), si = vertexSgn(0), snext;
  for (int i = 0; i < n; ++i, sprev = si, si = snext) {
    snext = vertexSgn(next(i, n));
    if (si == 0) {
      F t = static_cast<F>((poly[i] - line.a) * line.ab) / abs(line.ab);
      if (sprev == 0) {
        if (snext != 0 && snext == sgn((poly[i] - poly[prev(i, n)]) * line.ab))
          res += snext * t;
      } else {
        if ((snext != 0 && snext != sprev) ||
            (snext == 0 &&
             sprev == sgn((poly[next(i, n)] - poly[i]) * line.ab)))
          res -= sprev * t;
      }
    } else if (snext == -si) {
      auto vect = poly[next(i, n)] - poly[i];
      res +=
          snext * static_cast<F>((poly[i] - line.a) ^ vect) / (line.ab ^ vect);
    }
  }
  return res * norm(line.ab);
}
inline int read(Point<long long>& point) {
  double x, y;
  read(x, y);
  point.x = static_cast<long long>(x * 100 + sgn(x) * 0.5);
  point.y = static_cast<long long>(y * 100 + sgn(y) * 0.5);
  return 1;
}
int main() {
  input.reset(new InputFile(stdin, false));
  output.reset(new OutputFile());
  int n, m;
  read(n, m);
  Polygon<long long> poly(n);
  read((poly).begin(), (poly).end());
  if (!orientation(poly)) reverse(poly.begin() + 1, poly.end());
  for (int i(0), b_(m); i < b_; ++i) {
    Line<long long> line;
    read(line);
    printf("%.9lf\n", intersectLinePolygon(line, poly) / 100);
  }
  return 0;
}

```