Problem: This problem differs from the previous problem only in constraints.

Petya decided to visit Byteland during the summer holidays. It turned out that the history of this country is quite unusual.

Initially, there were n different countries on the land that is now Berland. Each country had its own territory that was represented as a rectangle on the map. The sides of the rectangle were parallel to the axes, and the corners were located at points with integer coordinates. Territories of no two countries intersected, but it was possible that some territories touched each other. As time passed, sometimes two countries merged into one. It only happened if the union of their territories was also a rectangle. In the end only one country remained — Byteland.

Initially, each country had a rectangular castle inside its territory. Its sides were parallel to the axes and its corners had integer coordinates. Some castles might touch the border of the corresponding country and sides or other castles. Miraculously, after all the unions the castles are still intact. Unfortunately, their locations are the only information we have to restore the initial territories of the countries.

<image> The possible formation of Byteland. The castles are shown in blue. 

Petya wonders why no information about the initial countries remained. He suspected that the whole story is a fake. You were recommended to him as a smart person. Please check whether or not there exists a possible set of initial territories that could make the story true.

Input

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the number of countries and castles.

Each of the next n lines contains four integers a_i, b_i, c_i, d_i (0 ≤ a_i < c_i ≤ 10^9, 0 ≤ b_i < d_i ≤ 10^9) — the coordinates of the i-th castle, where (a_i, b_i) are the coordinates of the lower left corner and (c_i, d_i) are the coordinates of the upper right corner.

It is guaranteed that no two castles intersect, however, they may touch.

Output

If there exists a possible set of territories that satisfies the story, print "YES", otherwise print "NO".

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

Examples

Input


4
0 0 1 2
0 2 1 3
1 0 2 1
1 1 2 3


Output


YES


Input


4
0 0 2 1
1 2 3 3
2 0 3 2
0 1 1 3


Output


NO

Note

The castles in the first and second examples are shown on the pictures below. 

<image> <image>

Solution (in JAVA):

Solution:
// package cf1181;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;

import static java.util.Comparator.comparingInt;

public class CFE1 {
    private static final String INPUT = "25\n" +
            "9666 2418 9939 6569\n" +
            "2193 1731 3327 1784\n" +
            "9603 1856 9658 6582\n" +
            "1512 8020 5665 8770\n" +
            "42 9695 1416 9935\n" +
            "1512 9507 9990 9699\n" +
            "8867 6617 9921 8791\n" +
            "1554 4745 8773 7948\n" +
            "9699 1893 9915 2357\n" +
            "75 9585 1418 9625\n" +
            "69 6664 825 9582\n" +
            "66 1883 819 6612\n" +
            "1516 1890 8754 4700\n" +
            "8572 8006 8746 8791\n" +
            "5342 8853 9974 9280\n" +
            "1542 9742 9996 9962\n" +
            "848 1880 1408 9560\n" +
            "8842 1867 9555 6573\n" +
            "5702 7992 8506 8797\n" +
            "15 1753 492 1798\n" +
            "51 58 9985 1715\n" +
            "3375 1758 9955 1794\n" +
            "529 1736 2187 1793\n" +
            "1502 9317 9972 9467\n" +
            "1496 8850 5280 9270";
    private static final int MOD = 1_000_000_007;

    private PrintWriter out;
    private FastScanner sc;

    public static void main(String[] args) {
        new CFE1().run();
    }

    public void run() {
        sc = new FastScanner(oj ? System.in : new ByteArrayInputStream(INPUT.getBytes()));
        out = new PrintWriter(System.out);

        long s = System.currentTimeMillis();
        solve();
        out.flush();
        tr(System.currentTimeMillis() - s + "ms");
    }

    static class Rect {
        int x1, y1, x2, y2;

        public Rect(int x1, int y1, int x2, int y2) {
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
        }

        @Override
        public String toString() {
            return "{" + x1 + "," + y1 + "-" + x2 + "," + y2 + "}";
        }
    }

    public void solve() {
        int n = sc.nextInt();
        Set<Rect> set = new TreeSet<>(comparingInt((Rect r) -> r.x1).thenComparingInt(r -> r.y1));
        for (int i = 0; i < n; i++) {
            Rect rect = new Rect(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt());
            set.add(rect);
        }

        int sol = solve(set);
        System.out.println(sol == n ? "YES" : "NO");
    }

    private int solve(Set<Rect> set) {
        if (set.size() < 4) return set.size();
        return _solve(set);
    }

    static class Recter {
        int i;
        Set<Rect> set;
        Iterator<Rect> it;
        Rect rect;
        int area;

        public Recter(Set<Rect> set) {
            this.i = 1;
            this.set = set;
            it = set.iterator();
            rect = it.next();
        }

        Rect next() {
            i++;
            return rect = it.next();
        }

        int size() {
            return set.size();
        }

        Set<Rect> drain() {
            Set<Rect> res = new TreeSet<>(comparingInt((Rect r) -> r.x1).thenComparingInt(r -> r.y1));
            Iterator<Rect> resIt = set.iterator();
            for (int i = 1; i < this.i; i++) {
                res.add(resIt.next());
                resIt.remove();
            }

            it = set.iterator();
            rect = it.next();
            i = 1;
            return res;
        }

        void clear(Set<Rect> rects) {
            for (Rect r : rects) {
                set.remove(r);
            }
            it = set.iterator();
            rect = it.next();
            i = 1;
        }
    }

    private int _solve(Set<Rect> setX1) {
        Recter rX1 = new Recter(setX1);
        TreeSet<Rect> setX2 = new TreeSet<>(comparingInt((Rect r1) -> -r1.x2).thenComparingInt(r1 -> -r1.y2));
        setX2.addAll(setX1);
        Recter rX2 = new Recter(setX2);

        TreeSet<Rect> setY1 = new TreeSet<>(comparingInt((Rect r1) -> r1.y1).thenComparingInt(r1 -> r1.x1));
        setY1.addAll(setX1);
        Recter rY1 = new Recter(setY1);

        TreeSet<Rect> setY2 = new TreeSet<>(comparingInt((Rect r) -> -r.y2).thenComparingInt(r -> -r.x2));
        setY2.addAll(setX1);
        Recter rY2 = new Recter(setY2);

        int result = 0;
        rX1.area = rX1.rect.x2;
        rX2.area = rX2.rect.x1;
        rY1.area = rY1.rect.y2;
        rY2.area = rY2.rect.y1;
        while (rX1.size() >= 4 && (rX1.i + rX2.i) <= rX1.size()) {
            rX1.next();
            if (rX1.rect.x1 >= rX1.area) {
                int n = rX1.i - 1;
                Set<Rect> set = rX1.drain();
                rX1.area = rX1.rect.x2;

                rX2.clear(set);
                rX2.area = rX2.rect.x1;

                rY1.clear(set);
                rY1.area = rY1.rect.y2;

                rY2.clear(set);
                rY2.area = rY2.rect.y1;

                int res = solve(set);
                if (res < n) return -1_000_000;
                result += res;
                continue;
            } else {
                rX1.area = Math.max(rX1.area, rX1.rect.x2);
            }

            rX2.next();
            if (rX2.rect.x2 <= rX2.area) {
                int n = rX2.i - 1;
                Set<Rect> set = rX2.drain();
                rX2.area = rX2.rect.x1;

                rX1.clear(set);
                rX1.area = rX1.rect.x2;

                rY1.clear(set);
                rY1.area = rY1.rect.y2;

                rY2.clear(set);
                rY2.area = rY2.rect.y1;

                int res = solve(set);
                if (res < n) return -1_000_000;
                result += res;
                continue;
            } else {
                rX2.area = Math.min(rX2.area, rX2.rect.x1);
            }

            rY1.next();
            if (rY1.rect.y1 >= rY1.area) {
                int n = rY1.i - 1;
                Set<Rect> set = rY1.drain();
                rY1.area = rY1.rect.y2;

                rY2.clear(set);
                rY2.area = rY2.rect.y1;

                rX1.clear(set);
                rX1.area = rX1.rect.x2;

                rX2.clear(set);
                rX2.area = rX2.rect.x1;

                int res = solve(set);
                if (res < n) return -1_000_000;
                result += res;
                continue;
            } else {
                rY1.area = Math.max(rY1.area, rY1.rect.y2);
            }

            rY2.next();
            if (rY2.rect.y2 <= rY2.area) {
                int n = rY2.i - 1;
                Set<Rect> set = rY2.drain();
                rY2.area = rY2.rect.y1;

                rY1.clear(set);
                rY1.area = rY1.rect.y2;

                rX1.clear(set);
                rX1.area = rX1.rect.x2;

                rX2.clear(set);
                rX2.area = rX2.rect.x1;

                int res = solve(set);
                if (res < n) return -1_000_000;
                result += res;
                continue;
            } else {
                rY2.area = Math.min(rY2.area, rY2.rect.y1);
            }
        }
        if (rX1.size() >= 4) {
            return result;
        } else {
            return result + rX1.size();
        }
    }

//********************************************************************************************
//********************************************************************************************
//********************************************************************************************

    static class SolutionFailedException extends Exception {
        int code;

        public SolutionFailedException(int code) {
            this.code = code;
        }
    }

    private static void shuffle(int[] array) {
        Random random = new Random();
        for (int i = array.length - 1; i > 0; i--) {
            int index = random.nextInt(i + 1);
            int temp = array[index];
            array[index] = array[i];
            array[i] = temp;
        }
    }

    /**
     * If searched element doesn't exist, returns index of first element which is bigger than searched value.<br>
     * If searched element is bigger than any array element function returns first index after last element.<br>
     * If searched element is lower than any array element function returns index of first element.<br>
     * If there are many values equals searched value function returns first occurrence.<br>
     */
    private static int lowerBound(long[] arr, long key) {
        int lo = 0;
        int hi = arr.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (key <= arr[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return arr[lo] < key ? lo + 1 : lo;
    }

    /**
     * Returns index of first element which is grater than searched value.
     * If searched element is bigger than any array element, returns first index after last element.
     */
    private static int upperBound(long[] arr, long key) {
        int lo = 0;
        int hi = arr.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (key >= arr[mid]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return arr[lo] <= key ? lo + 1 : lo;
    }

    private static int ceil(double d) {
        int ret = (int) d;
        return ret == d ? ret : ret + 1;
    }

    private static int round(double d) {
        return (int) (d + 0.5);
    }

    private static int gcd(int a, int b) {
        BigInteger b1 = BigInteger.valueOf(a);
        BigInteger b2 = BigInteger.valueOf(b);
        BigInteger gcd = b1.gcd(b2);
        return gcd.intValue();
    }

    private static long gcd(long a, long b) {
        BigInteger b1 = BigInteger.valueOf(a);
        BigInteger b2 = BigInteger.valueOf(b);
        BigInteger gcd = b1.gcd(b2);
        return gcd.longValue();
    }

    private int[] readIntArray(int n) {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = sc.nextInt();
        }
        return res;
    }

    private long[] readLongArray(int n) {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = sc.nextLong();
        }
        return res;
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        FastScanner(InputStream stream) {
            this.stream = stream;
        }

        int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) return -1;
            }
            return buf[curChar++];
        }

        boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        boolean isEndline(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public String nextLine() {
            int c = read();
            while (isEndline(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndline(c));
            return res.toString();
        }

    }

    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

    private void tr(Object... o) {
        if (!oj) System.out.println(Arrays.deepToString(o));
    }
}