You are given two squares, one with sides parallel to the coordinate axes, and another one with sides at 45 degrees to the coordinate axes. Find whether the two squares intersect.

The interior of the square is considered to be part of the square, i.e. if one square is completely inside another, they intersect. If the two squares only share one common point, they are also considered to intersect.

Input

The input data consists of two lines, one for each square, both containing 4 pairs of integers. Each pair represents coordinates of one vertex of the square. Coordinates within each line are either in clockwise or counterclockwise order.

The first line contains the coordinates of the square with sides parallel to the coordinate axes, the second line contains the coordinates of the square at 45 degrees.

All the values are integer and between -100 and 100.

Output

Print "Yes" if squares intersect, otherwise print "No".

You can print each letter in any case (upper or lower).

Examples

Input

0 0 6 0 6 6 0 6
1 3 3 5 5 3 3 1


Output

YES


Input

0 0 6 0 6 6 0 6
7 3 9 5 11 3 9 1


Output

NO


Input

6 0 6 6 0 6 0 0
7 4 4 7 7 10 10 7


Output

YES

Note

In the first example the second square lies entirely within the first square, so they do intersect.

In the second sample squares do not have any points in common.

Here are images corresponding to the samples:

<image> <image> <image>
#include <bits/stdc++.h>
const double eps = 1e-8;
inline int dcmp(double x) { return x < -eps ? -1 : x > eps; }
struct Point;
using Vector = Point;
using Polygon = std::vector<Point>;
struct Point {
  double x, y;
  Point() {}
  Point(double _x, double _y) : x(_x), y(_y) {}
  Point operator+(const Point &rhs) const {
    return Point(x + rhs.x, y + rhs.y);
  }
  Point operator-(const Point &rhs) const {
    return Point(x - rhs.x, y - rhs.y);
  }
  Point operator*(double t) const { return Point(x * t, y * t); }
  bool operator==(const Point &rhs) const {
    return dcmp(x - rhs.x) == 0 && dcmp(y - rhs.y) == 0;
  }
  double length() const { return hypot(x, y); }
  void read() { scanf("%lf%lf", &x, &y); }
  Point rotate(const Point &o, double angle) const {
    Point t = (*this) - o;
    double c = cos(angle), s = sin(angle);
    return Point(o.x + t.x * c - t.y * s, o.y + t.x * s + t.y * c);
  }
  Vector normal() const {
    double L = length();
    return Vector(-y / L, x / L);
  }
};
double det(const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; }
double dot(const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; }
bool polar_cmp(const Point &a, const Point &b) {
  if (dcmp(a.y) * dcmp(b.y) <= 0) {
    if (dcmp(a.y) > 0 || dcmp(b.y) > 0) return dcmp(a.y - b.y) < 0;
    if (dcmp(a.y) == 0 && dcmp(b.y) == 0) return dcmp(a.x - b.x) < 0;
  }
  return dcmp(det(a, b)) > 0;
}
Point intersection_line_line(Point p, Vector v, Point q, Vector w) {
  Vector u = p - q;
  double t = det(w, u) / det(v, w);
  return p + v * t;
}
double distance_point_line(Point p, Point a, Point b) {
  Vector v1 = b - a, v2 = p - a;
  return std::abs(det(v1, v2)) / v1.length();
}
double distance_point_segment(Point p, Point a, Point b) {
  if (a == b) return (p - a).length();
  Vector v1 = b - a, v2 = p - a, v3 = p - b;
  if (dcmp(dot(v1, v2)) < 0)
    return v2.length();
  else if (dcmp(dot(v1, v3)) > 0)
    return v3.length();
  else
    return std::abs(det(v1, v2)) / v1.length();
}
Point projection_point_line(Point p, Point a, Point b) {
  Vector v = b - a;
  return a + v * (dot(v, p - a) / dot(v, v));
}
bool intersection_segment_segment(Point a1, Point a2, Point b1, Point b2) {
  double c1 = det(a2 - a1, b1 - a1), c2 = det(a2 - a1, b2 - a1),
         c3 = det(b2 - b1, a1 - b1), c4 = det(b2 - b1, a2 - b1);
  return dcmp(c1) * dcmp(c2) <= 0 && dcmp(c3) * dcmp(c4) <= 0;
}
bool on_point_segment(Point p, Point a1, Point a2) {
  return dcmp(det(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) <= 0;
}
bool in_point_polygon(Point o, const Polygon &poly, bool flag) {
  int t = 0;
  Point a, b;
  int n = poly.size();
  for (int i = 0; i < n; ++i) {
    if (on_point_segment(o, poly[i], poly[(i + 1) % n])) return flag;
  }
  for (int i = 0; i < n; ++i) {
    a = poly[i];
    b = poly[(i + 1) % n];
    if (dcmp(a.y - b.y) > 0) std::swap(a, b);
    if (dcmp(det(a - o, b - o)) < 0 && dcmp(a.y - o.y) < 0 &&
        dcmp(o.y - b.y) <= 0)
      ++t;
  }
  return t & 1;
}
Polygon poly[2];
int next(int x) { return (x + 1) % 4; }
bool check() {
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 4; ++j) {
      if (in_point_polygon(poly[i][j], poly[i ^ 1], true)) return true;
    }
  }
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      if (intersection_segment_segment(poly[0][i], poly[0][next(i)], poly[1][j],
                                       poly[1][next(j)]))
        return true;
    }
  }
  return false;
}
int main() {
  for (int i = 0; i < 2; ++i) {
    poly[i].resize(4);
    for (int j = 0; j < 4; ++j) {
      poly[i][j].read();
    }
  }
  puts(check() ? "YES" : "NO");
}
