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>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Locale;
import java.util.StringTokenizer;

public class Main {
    class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    int area(Point a, Point b, Point c) {
        return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    }

    boolean intersect_1(int a, int b, int c, int d) {
        if (a > b) {
            int t = a;
            a = b;
            b = t;
        }
        if (c > d) {
            int t = c;
            c = d;
            d = t;
        }
        return Math.max(a, c) <= Math.min(b, d);
    }

    boolean intersect(Point a, Point b, Point c, Point d) {
        return intersect_1(a.x, b.x, c.x, d.x)
                && intersect_1(a.y, b.y, c.y, d.y)
                && area(a, b, c) * area(a, b, d) <= 0
                && area(c, d, a) * area(c, d, b) <= 0;
    }

    class line {
        int a, b, c;

        line(Point p, Point q) {
            a = p.y - q.y;
            b = q.x - p.x;
            c = -1 * (a * p.x + b * p.y);
        }

        int get(Point p) {
            return a * p.x + b * p.y + c;
        }
    }

    int sign(int x) {
        if (x > 0) return 1;
        if (x < 0) return -1;
        return 0;
    }

    public void solve() throws IOException {
        Point p1[] = new Point[4];
        Point p2[] = new Point[4];
        int mid1x = 0, mid2x = 0, mid1y = 0, mid2y = 0;
        int maxx = Integer.MIN_VALUE, maxy = Integer.MIN_VALUE, minx = Integer.MAX_VALUE, miny = Integer.MAX_VALUE;
        for (int i = 0; i < 4; i++) {
            p1[i] = new Point(2 * nextInt(), 2 * nextInt());
            maxx = Math.max(maxx, p1[i].x);
            minx = Math.min(minx, p1[i].x);
            maxy = Math.max(maxy, p1[i].y);
            miny = Math.min(miny, p1[i].y);
            if (i % 2 == 0) {
                mid1x += p1[i].x;
                mid1y += p1[i].y;
            }
        }
        for (int i = 0; i < 4; i++) {
            p2[i] = new Point(2 * nextInt(), 2 * nextInt());
            if (i % 2 == 0) {
                mid2x += p2[i].x;
                mid2y += p2[i].y;
            }
        }
        mid1x /= 2;
        mid1y /= 2;
        mid2x /= 2;
        mid2y /= 2;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (intersect(p1[i], p1[(i + 1) % 4], p2[j], p2[(j + 1) % 4])) {
                    out.print("YES");
                    return;
                }
            }
        }
        if (mid2x >= minx && mid2x <= maxx && mid2y >= miny && mid2y <= maxy) {
            out.print("YES");
            return;
        }
        line l1 = new line(p2[0], p2[1]), l2 = new line(p2[3], p2[2]);
        Point mid = new Point(mid1x, mid1y);

        line l3 = new line(p2[1], p2[2]);
        line l4 = new line(p2[0], p2[3  ]);
        if (sign(l1.get(mid)) != sign(l2.get(mid)) && sign(l3.get(mid)) != sign(l4.get(mid))) {
            out.print("YES");
            return;
        }

        out.print("NO");

    }

    BufferedReader br;
    StringTokenizer sc;
    PrintWriter out;

    public static void main(String[] args) throws IOException {
        Locale.setDefault(Locale.US);
        new Main().run();
    }

    public void run() throws IOException {
        try {
            br = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            solve();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    public String nextToken() throws IOException {
        while (sc == null || !sc.hasMoreTokens()) {
            try {
                sc = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                return null;
            }
        }
        return sc.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
}
