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.util.*;
import java.lang.*;
import java.io.*;

// Created by @thesupremeone on 28/07/21
public class Main {
    static class Point{
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static class Line{
        Point p1, p2;
        public Line(Point p1, Point p2) {
            this.p1 = p1;
            this.p2 = p2;
        }
        int side(Point point){
            return Double.compare((point.y-p1.y)*(p2.x-p1.x),
                    (p2.y-p1.y)*(point.x-p1.x));
        }
    }
    boolean sameSide(Line line, Point refPoint, Point point){
        if(line.side(point)==0)
            return true;
        return line.side(refPoint)==line.side(point);
    }
    boolean lies(Point[] square, Point point){
        int start=0;
        do {
            int end = (start+1)%4;
            int ref = (end+1)%4;
            Line line = new Line(square[start], square[end]);
            if(!sameSide(line, square[ref], point)){
                return false;
            }
            start = (start+1)%4;
        }while (start!=0);
        return true;
    }

    boolean checkAllPoints(Point[] square1, Point[] square2){
        int lowX = Math.min(square1[0].x, square1[2].x);
        int highX = Math.max(square1[0].x, square1[2].x);
        int lowY = Math.min(square1[0].y, square1[2].y);
        int highY = Math.max(square1[0].y, square1[2].y);
        for (int i = lowX; i <= highX; i++) {
            for (int j = lowY; j <= highY; j++) {
                if(lies(square2, new Point(i,j))){
                    return true;
                }
            }
        }
        return false;
    }

    void solve() throws IOException {
        Point[] square1 = new Point[4];
        for (int i = 0; i < 4; i++) {
            int x = getInt();
            int y = getInt();
            square1[i] = new Point(x, y);
        }
        Point[] square2 = new Point[4];
        for (int i = 0; i < 4; i++) {
            int x = getInt();
            int y = getInt();
            square2[i] = new Point(x, y);
        }
        boolean ans = false;
        for (Point point : square2){
            ans = lies(square1, point);
            if(ans) break;
        }
        if(ans || checkAllPoints(square1, square2)){
            println("YES");
        }else {
            println("NO");
        }
    }

    public static void main(String[] args) throws Exception {
        if (isOnlineJudge()) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new BufferedWriter(new OutputStreamWriter(System.out));
            new Main().solve();
            out.flush();
        } else {
            localJudge = new Thread();
            in = new BufferedReader(new FileReader("input.txt"));
            out = new BufferedWriter(new FileWriter("output.txt"));
            localJudge.start();
            new Main().solve();
            out.flush();
            localJudge.suspend();
        }
    }
    static boolean isOnlineJudge(){
        try {
            return System.getProperty("ONLINE_JUDGE")!=null
                    || System.getProperty("LOCAL")==null;
        }catch (Exception e){
            return true;
        }
    }
    // Fast Input & Output
    static Thread localJudge = null;
    static BufferedReader in;
    static StringTokenizer st;
    static BufferedWriter out;
    static String getLine() throws IOException{
        return in.readLine();
    }
    static String getToken() throws IOException{
        if(st==null || !st.hasMoreTokens())
            st = new StringTokenizer(getLine());
        return st.nextToken();
    }
    static int getInt() throws IOException {
        return Integer.parseInt(getToken());
    }
    static long getLong() throws IOException {
        return Long.parseLong(getToken());
    }
    static void print(Object s) throws IOException{
        out.write(String.valueOf(s));
    }
    static void println(Object s) throws IOException{
        out.write(String.valueOf(s));
        out.newLine();
    }
}