p03685 AtCoder Regular Contest 076 - Connected?_16128
Snuke is playing a puzzle game. In this game, you are given a rectangular board of dimensions R × C, filled with numbers. Each integer i from 1 through N is written twice, at the coordinates (x_{i,1},y_{i,1}) and (x_{i,2},y_{i,2}).

The objective is to draw a curve connecting the pair of points where the same integer is written, for every integer from 1 through N. Here, the curves may not go outside the board or cross each other.

Determine whether this is possible.

Constraints

* 1 ≤ R,C ≤ 10^8
* 1 ≤ N ≤ 10^5
* 0 ≤ x_{i,1},x_{i,2} ≤ R(1 ≤ i ≤ N)
* 0 ≤ y_{i,1},y_{i,2} ≤ C(1 ≤ i ≤ N)
* All given points are distinct.
* All input values are integers.

Input

Input is given from Standard Input in the following format:


R C N
x_{1,1} y_{1,1} x_{1,2} y_{1,2}
:
x_{N,1} y_{N,1} x_{N,2} y_{N,2}


Output

Print `YES` if the objective is achievable; print `NO` otherwise.

Examples

Input

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


Output

YES


Input

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


Output

NO


Input

5 5 7
0 0 2 4
2 3 4 5
3 5 5 2
5 5 5 4
0 3 5 1
2 2 4 4
0 5 4 1


Output

YES


Input

1 1 2
0 0 1 1
1 0 0 1


Output

NO
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int R, C, N;
    static Pair[] P;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        N = sc.nextInt();

        P = new Pair[N];
        for (int i = 0; i < N; i++) {
            P[i] = new Pair(new Cord(sc.nextInt(), sc.nextInt(), i), new Cord(sc.nextInt(), sc.nextInt(), i) );
        }

        System.out.println(solve() ? "YES" : "NO");
    }

    static class Pair {
        Cord a;
        Cord b;

        public Pair(Cord a, Cord b) {
            this.a = a;
            this.b = b;
        }
    }

    static class Cord implements Comparable<Cord> {
        int x, y, i;

        public Cord(int x, int y, int i) {
            this.x = x;
            this.y = y;
            this.i = i;
        }

        public String toString() {
            return "(" + x + "," + y + "," + i + ")";
        }

        @Override
        public int compareTo(Cord c) {
            int t = type();
            int ct = c.type();
            if( t != ct ) {
                return Integer.compare(t, ct);
            }

            if( t == 1 ) {
                return Integer.compare(y, c.y);
            } else if( t == 2 ) {
                return Integer.compare(x, c.x);
            } else if( t == 3 ) {
                return Integer.compare(c.y, y);
            } else {
                return Integer.compare(c.x, x);
            }
        }

        int type() {
            if( x == 0 ) {
                return 1;
            } else if ( y == C ) {
                return 2;
            } else if( x == R ) {
                return 3;
            } else if( y == 0 ) {
                return 4;
            } else {
                throw new RuntimeException("wtf : " + x + " " + y);
            }
        }

        public boolean isOnEdge() {
            return x == 0 || y == 0 || x == R || y == C;
        }
    }

    static boolean solve() {
        List<Cord> onEdges = new ArrayList<>();
        for (Pair pair : P) {
            if( pair.a.isOnEdge() && pair.b.isOnEdge() ) {
                onEdges.add(pair.a);
                onEdges.add(pair.b);
            }
        }

        onEdges.sort(Comparator.naturalOrder());

        // System.out.println( onEdges );

        Set<Integer> set = new HashSet<>();
        LinkedList<Cord> stack = new LinkedList<>();

        for (Cord c : onEdges) {
            if( !set.contains(c.i) ) {
                stack.addFirst(c);
                set.add(c.i);
            } else {
                Cord inStack = stack.removeFirst();
                if( inStack.i != c.i ) return false;
            }
        }
        return true;
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

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

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

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}
