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>
using namespace std;
const char nl = '\n';
const int INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3f;
const long long MOD = 1e9 + 7;
const long double EPS = 1e-10;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long double cp(const complex<long double>& a, const complex<long double>& b) {
  return imag(conj(a) * b);
}
long double dp(const complex<long double>& a, const complex<long double>& b) {
  return real(conj(a) * b);
}
inline bool eq(const complex<long double>& a, const complex<long double>& b) {
  return abs(a - b) < EPS;
}
inline long double sgn(const long double& x) {
  return abs(x) < EPS ? 0 : x / abs(x);
}
inline bool cmp_lex(const complex<long double>& a,
                    const complex<long double>& b) {
  return a.real() < b.real() - EPS ||
         (a.real() < b.real() + EPS && a.imag() < b.imag() - EPS);
}
inline bool cmp_lex_i(const complex<long double>& a,
                      const complex<long double>& b) {
  return a.imag() < b.imag() - EPS ||
         (a.imag() < b.imag() + EPS && a.real() < b.real() - EPS);
}
bool seg_x_seg(complex<long double> a1, complex<long double> a2,
               complex<long double> b1, complex<long double> b2) {
  long double za = abs(a2 - a1), zb = abs(b2 - b1);
  za = za > EPS ? 1 / za : 0;
  zb = zb > EPS ? 1 / zb : 0;
  int s1 = sgn(cp(a2 - a1, b1 - a1) * za), s2 = sgn(cp(a2 - a1, b2 - a1) * za);
  int s3 = sgn(cp(b2 - b1, a1 - b1) * zb), s4 = sgn(cp(b2 - b1, a2 - b1) * zb);
  if (!s1 && !s2 && !s3) {
    if (cmp_lex(a2, a1)) swap(a1, a2);
    if (cmp_lex(b2, b1)) swap(b1, b2);
    return !cmp_lex(b2, a1) && !cmp_lex(a2, b1);
  }
  return s1 * s2 <= 0 && s3 * s4 <= 0;
}
inline bool on_segment(const complex<long double>& a,
                       const complex<long double>& b,
                       const complex<long double>& p) {
  return abs(cp(b - a, p - a)) < EPS && dp(b - a, p - a) > 0 &&
         dp(a - b, p - b) > 0;
}
inline bool on_boundary(const vector<complex<long double> >& v,
                        const complex<long double>& p) {
  bool res = false;
  for (int i = v.size() - 1, j = 0; j < v.size(); i = j++)
    res |= on_segment(v[i], v[j], p) | (abs(p - v[i]) < EPS);
  return res;
}
bool pt_in_polygon(const complex<long double>& p,
                   const vector<complex<long double> >& v) {
  if (on_boundary(v, p)) return true;
  long double res = 0;
  for (int i = v.size() - 1, j = 0; j < v.size(); i = j++)
    res += atan2(cp(v[i] - p, v[j] - p), dp(v[i] - p, v[j] - p));
  return abs(res) > 1;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  vector<complex<long double> > a, b;
  int x, y;
  for (int i = 0; i < 4; i++) {
    cin >> x >> y;
    a.push_back(complex<long double>(x, y));
  }
  for (int i = 0; i < 4; i++) {
    cin >> x >> y;
    b.push_back(complex<long double>(x, y));
  }
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      if (seg_x_seg(a[i], a[(i + 1) % 4], b[j], b[(j + 1) % 4])) {
        cout << "YES" << nl;
        return 0;
      }
    }
  }
  for (int i = 0; i < 4; i++) {
    if (pt_in_polygon(a[i], b) || pt_in_polygon(b[i], a)) {
      cout << "YES" << nl;
      return 0;
    }
  }
  cout << "NO" << nl;
  return 0;
}
