Problem: Note that the difference between easy and hard versions is that in hard version unavailable cells can become available again and in easy version can't. You can make hacks only if all versions are solved.

Ildar and Ivan are tired of chess, but they really like the chessboard, so they invented a new game. The field is a chessboard 2n × 2m: it has 2n rows, 2m columns, and the cell in row i and column j is colored white if i+j is even, and is colored black otherwise.

The game proceeds as follows: Ildar marks some of the white cells of the chessboard as unavailable, and asks Ivan to place n × m kings on the remaining white cells in such way, so that there are no kings attacking each other. A king can attack another king if they are located in the adjacent cells, sharing an edge or a corner.

Ildar would like to explore different combinations of cells. Initially all cells are marked as available, and then he has q queries. In each query he marks a cell as unavailable. After each query he would like to know whether it is possible to place the kings on the available cells in a desired way. Please help him!

Input

The first line of input contains three integers n, m, q (1 ≤ n, m, q ≤ 200 000) — the size of the board and the number of queries.

q lines follow, each of them contains a description of a query: two integers i and j, denoting a white cell (i, j) on the board (1 ≤ i ≤ 2n, 1 ≤ j ≤ 2m, i + j is even) that becomes unavailable. It's guaranteed, that each cell (i, j) appears in input at most once.

Output

Output q lines, i-th line should contain answer for a board after i queries of Ildar. This line should contain "YES" if it is possible to place the kings on the available cells in the desired way, or "NO" otherwise.

Examples

Input


1 3 3
1 1
1 5
2 4


Output


YES
YES
NO


Input


3 2 7
4 2
6 4
1 3
2 2
2 4
4 4
3 1


Output


YES
YES
NO
NO
NO
NO
NO

Note

In the first example case after the second query only cells (1, 1) and (1, 5) are unavailable. Then Ivan can place three kings on cells (2, 2), (2, 4) and (2, 6).

After the third query three cells (1, 1), (1, 5) and (2, 4) are unavailable, so there remain only 3 available cells: (2, 2), (1, 3) and (2, 6). Ivan can not put 3 kings on those cells, because kings on cells (2, 2) and (1, 3) attack each other, since these cells share a corner.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.io.IOException;
import java.util.Random;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.StringTokenizer;
import java.util.Map;
import java.io.BufferedReader;
import java.io.InputStream;
import java.util.function.IntFunction;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        F2ChessStrikesBackHardVersion solver = new F2ChessStrikesBackHardVersion();
        solver.solve(1, in, out);
        out.close();
    }

    static class F2ChessStrikesBackHardVersion {
        private static final String NO = "NO";
        private static final String YES = "YES";

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            in.nextInt(); // unused, N
            in.nextInt(); // unused, M
            int queries = in.nextInt();
            Pii[] q = new Pii[queries];
            for (int i = 0; i < queries; i++) {
                q[i] = Pii.of(in.nextInt() - 1, in.nextInt() - 1);
            }
            Map<Integer, Integer> xCoord = coordinatesMap(q);
            final int X = xCoord.size();

            int powerOfTwo = Integer.highestOneBit(X);
            if (powerOfTwo < X)
                powerOfTwo *= 2;
            FastSegmentTree<F2ChessStrikesBackHardVersion.T> st = new FastSegmentTree<>(powerOfTwo, F2ChessStrikesBackHardVersion.T::new);
            TreeSet<Integer>[] fY = new TreeSet[X];
            TreeSet<Integer>[] bY = new TreeSet[X];
            for (int x = 0; x < X; x++) {
                fY[x] = new TreeSet<>();
                fY[x].add(Integer.MAX_VALUE);
            }
            for (int x = 0; x < X; x++) {
                bY[x] = new TreeSet<>();
                bY[x].add(Integer.MIN_VALUE);
            }

            for (Pii p : q) {
                boolean isForward = p.first % 2 == 0;
                int x = xCoord.get(p.first);

                TreeSet<Integer> y = isForward ? fY[x] : bY[x];
                boolean remove = y.contains(p.second);

                if (remove) {
                    y.remove(p.second);
                } else {
                    y.add(p.second);
                }

                st.get(x);
                if (isForward)
                    st.value.min[0] = y.first();
                else
                    st.value.max[0] = y.last();
                st.update(x);

                boolean valid = !st.value.bad[1];
                out.println(valid ? YES : NO);
            }
        }

        private static Map<Integer, Integer> coordinatesMap(Pii[] q) {
            int[] coordinateArray = new int[q.length];
            for (int i = 0; i < q.length; i++) {
                coordinateArray[i] = q[i].first;
            }
            Util.safeSort(coordinateArray);
            Map<Integer, Integer> coordinates = new HashMap<>();
            for (int i = 0, j = 0; i < coordinateArray.length; i++) {
                if (coordinates.containsKey(coordinateArray[i]))
                    continue;
                coordinates.put(coordinateArray[i], j++);
            }
            return coordinates;
        }

        private static class T implements FastSegmentTree.Storage<F2ChessStrikesBackHardVersion.T> {
            public final int[] min;
            public final int[] max;
            public final boolean[] bad;

            public T(int capacity) {
                min = new int[capacity];
                max = new int[capacity];
                bad = new boolean[capacity];
            }

            public void clear(int i) {
                min[i] = Integer.MAX_VALUE;
                max[i] = Integer.MIN_VALUE;
                bad[i] = false;
            }

            public void set(int to, int from) {
                min[to] = min[from];
                max[to] = max[from];
                bad[to] = bad[from];
            }

            public void combine(int target, int left, int right) {
                min[target] = Math.min(min[left], min[right]);
                max[target] = Math.max(max[left], max[right]);
                bad[target] = bad[left] || bad[right] || min[left] < max[right];
            }

        }

    }

    static class Pii implements Comparable<Pii> {
        public final int first;
        public final int second;

        public Pii(int first, int second) {
            this.first = first;
            this.second = second;
        }

        public static Pii of(int first, int second) {
            return new Pii(first, second);
        }

        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Pii pair = (Pii) o;
            return first == pair.first && second == pair.second;
        }

        public int hashCode() {
            return Arrays.hashCode(new int[]{first, second});
        }

        public String toString() {
            return "(" + first + ", " + second + ')';
        }

        public int compareTo(Pii o) {
            if (first != o.first)
                return Integer.compare(first, o.first);
            return Integer.compare(second, o.second);
        }

    }

    static class InputReader {
        public final BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

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

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

    }

    static class Util {
        public static void safeSort(int[] x) {
            shuffle(x);
            Arrays.sort(x);
        }

        public static void shuffle(int[] x) {
            Random r = new Random();

            for (int i = 0; i <= x.length - 2; i++) {
                int j = i + r.nextInt(x.length - i);
                swap(x, i, j);
            }
        }

        public static void swap(int[] x, int i, int j) {
            int t = x[i];
            x[i] = x[j];
            x[j] = t;
        }

        private Util() {
        }

    }

    static class FastSegmentTree<T extends FastSegmentTree.Storage<T>> {
        public final int size;
        public final T value;

        public FastSegmentTree(int size, IntFunction<T> constructor) {
            this.size = size;
            value = constructor.apply(2 * size + 4);
            for (int i = 0; i < 2 * size + 2; i++) {
                value.clear(i);
            }
        }

        public void get(int i) {
            value.set(0, size + i);
        }

        public void update(int i) {
            i += size;
            value.set(i, 0);
            while (i > 1) {
                i /= 2;
                value.combine(i, 2 * i, 2 * i + 1);
            }
        }

        public interface Storage<T extends FastSegmentTree.Storage<T>> {
            void clear(int i);

            void set(int to, int from);

            void combine(int target, int left, int right);

        }

    }
}