## 1. Abridged Problem Statement

You are given an `n × m` grid of cells, with `k` marked cells. You may repeatedly fold the paper along a line between two adjacent rows or between two adjacent columns. After each fold, the folded paper is treated as the new paper.

Determine whether it is possible to perform folds so that all marked cells end up exactly on top of each other, and no unmarked cell is in that same stack.

Output `"YES"` if possible, otherwise `"NO"`.

---

## 2. Detailed Editorial

### Key observation: rows and columns are independent

A fold along a horizontal line affects only row indices.
A fold along a vertical line affects only column indices.

Suppose all marked cells finally lie in one stack. Then:

- all marked rows must be foldable into one row stack,
- all marked columns must be foldable into one column stack.

However, there is one more important condition.

Let:

- `R` be the set of row indices that contain at least one marked cell,
- `C` be the set of column indices that contain at least one marked cell.

If all rows in `R` are folded together and all columns in `C` are folded together, then every original cell in `R × C` will end up in the final marked stack.

Therefore, every cell in the Cartesian product `R × C` must be marked.

So the problem reduces to:

1. Check whether the set of marked rows is foldable in 1D.
2. Check whether the set of marked columns is foldable in 1D.
3. Check whether the marked cells form exactly the full grid product `R × C`.

---

### The 1D problem

We are given a strip of length `lim`, and a sorted set of marked positions `v`.

We need to know if all marked positions can be folded into one stack without including any unmarked position.

The function `foldable_1d(v, lim)` checks this.

---

### Necessary parity condition

When folding between two adjacent cells, the reflection maps a position `x` to:

```text
x' = constant - x
```

The two reflected positions always have an odd sum, meaning their distance is odd.

Therefore, two consecutive marked positions must be separated by an odd distance.

If any consecutive difference is even, folding is impossible.

Example:

```text
marked positions: 1 and 3
distance = 2
```

There is one unmarked cell between them, and they cannot be merged without including it.

---

### Removing border runs

If marked cells form a consecutive run starting from the left border:

```text
1, 2, 3, ...
```

they can be folded inward safely.

Similarly, a consecutive run touching the right border:

```text
..., lim - 2, lim - 1, lim
```

can be removed from consideration.

The algorithm removes such border-touching marked runs.

---

### Internal runs

After removing border runs, the remaining marked positions are split into runs of consecutive marked cells.

Example:

```text
marked positions: 4 5 8 12 13
runs: [4,5], [8], [12,13]
run lengths: 2, 1, 2
gaps: 3, 4
```

An internal consecutive run of marked cells with length greater than `1` must have even length.

Why?

An even-length internal run can be folded around its center line, which lies between two cells.

An odd-length internal run would have its center on a cell, not between cells, so it cannot be folded symmetrically without mixing marked and unmarked cells.

Thus:

```cpp
if(run_len > 1 && run_len is odd)
    impossible
```

---

### Isolated single marked cells

The difficult case is isolated marked cells, that is, internal runs of length `1`.

Between two consecutive isolated single marked cells, the sequence of runs and gaps between them must be a palindrome.

Why?

If two isolated marks are to be merged, the fold line must be exactly halfway between them. This reflection maps the structure between them onto itself. Therefore, the pattern of marked runs and gaps between them must be symmetric.

The algorithm builds a sequence like:

```text
run_length, gap, run_length, gap, run_length, ...
```

Then for each pair of consecutive `run_length == 1`, it checks that the part between them is palindromic.

If all these checks pass, the 1D set is foldable.

---

### Final rectangular-product check

Even if row and column sets are individually foldable, the marked cells must form a complete rectangle over those row and column sets.

For example:

```text
marked cells:
(1,1), (1,4), (4,1), (4,4)
```

Rows are `{1,4}`, columns are `{1,4}`, and all four combinations exist, so the answer is `"YES"`.

But:

```text
marked cells:
(1,1), (1,4), (4,1)
```

Rows are `{1,4}`, columns are `{1,4}`, but `(4,4)` is missing, so folding would put an unmarked cell into the marked stack. The answer is `"NO"`.

---

### Complexity

Let `k` be the number of marked cells.

Sorting rows, columns, and cells dominates the complexity.

```text
Time complexity:  O(k log k)
Memory complexity: O(k)
```

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
}

int n, m, k;
vector<pair<int, int>> pts;

void read() {
    cin >> n >> m >> k;
    pts.resize(k);
    cin >> pts;
}

bool foldable_1d(vector<int>& v, int lim) {
    int s = (int)v.size();
    if(s < 2) {
        return true;
    }

    for(int i = 1; i < s; i++) {
        if(((v[i] - v[i - 1]) & 1) == 0) {
            return false;
        }
    }

    int low = 0, high = s;
    int left_border = 1, right_border = lim;
    while(low < high && v[low] == left_border) {
        low++;
        left_border++;
    }

    while(low < high && v[high - 1] == right_border) {
        high--;
        right_border--;
    }

    vector<int> seq;
    for(int i = low; i < high;) {
        int j = i;
        while(j + 1 < high && v[j + 1] == v[j] + 1) {
            j++;
        }

        int run_len = j - i + 1;
        if(run_len > 1 && (run_len & 1)) {
            return false;
        }

        seq.push_back(run_len);
        if(j + 1 < high) {
            seq.push_back(v[j + 1] - v[j]);
        }

        i = j + 1;
    }

    int prev = -1;
    for(int k = 0; k < (int)seq.size(); k += 2) {
        if(seq[k] != 1) {
            continue;
        }

        if(prev >= 0) {
            for(int l = prev + 1, r = k - 1; l < r; l++, r--) {
                if(seq[l] != seq[r]) {
                    return false;
                }
            }
        }

        prev = k;
    }

    return true;
}

bool is_full_grid(vector<pair<int, int>>& cells, vector<int>& cols) {
    int n_cells = (int)cells.size();
    int n_cols = (int)cols.size();
    if(n_cells == 0) {
        return true;
    }
    if(n_cells % n_cols != 0) {
        return false;
    }
    int n_rows = n_cells / n_cols;
    for(int row_idx = 0; row_idx < n_rows; row_idx++) {
        int expected_row = cells[row_idx * n_cols].first;
        for(int col_idx = 0; col_idx < n_cols; col_idx++) {
            const auto& cell = cells[row_idx * n_cols + col_idx];
            if(cell.first != expected_row || cell.second != cols[col_idx]) {
                return false;
            }
        }
    }
    return true;
}

void solve() {
    // The core idea is that folds act independently on rows and columns.
    // Each fold is a reflection across a line that sits exactly between
    // two adjacent cells (a half-integer position). Also, any two positions
    // that can ever be stacked on top of each other must have an odd difference
    // (their sum is always odd).
    //
    // Therefore the set of distinct row indices (and separately the distinct
    // column indices) must satisfy several intuitive folding rules:
    //
    //     - All gaps between consecutive marked positions are odd
    //       (reflection invariant).
    //
    //     - Runs that touch the border (position 1 or n) can be peeled
    //       away one cell at a time.
    //
    //     - Any internal run of length > 1 must be even. Only then is the
    //       fold-line at the centre of the run between two cells, and folding
    //       there pairs marks with marks and the unmarked neighbours of the
    //       run with each other. The result is a half-length run flush against
    //       the new border, which the previous rule then peels.
    //       An odd-length internal run has no central fold line and
    //       inevitably drags an unmarked cell onto a marked one.
    //
    //     - For each pair of consecutive isolated single marks, the
    //       run-and-gap pattern strictly between them must be a palindrome.
    //       The only fold that merges two isolated marks at positions p
    //       and q is along the line equidistant from both (valid because
    //       the gap is odd), and that fold reflects the cells between
    //       them pairwise from the outside in. For the reflection to map
    //       mark onto mark and gap onto gap, the pattern in between has
    //       to mirror around the midpoint.
    //
    // Some intuition for the exact construction on how to do the folding is
    // that we can look at the left side and try to fold it by going to the
    // right. We can fold both a marked and unmarked groups that touch the
    // border into size one: say we start with unmarked and convert it to a one
    // size unmarked, followed by some K marked cells, and then B marked. We
    // will fold the K marked in the middle so now the resulting sequence starts
    // with K/2 marked, followed by B >= 1 unmarked. We can continue folding by
    // 1, getting to a 1 marked cell as the start, followed by B unmarked. Then
    // to get rid of the 1 marked, we fold the B unmarked in two. We can notice
    // that this logic breaks only when K = 1, as then we can't fold the marked
    // cells. We can collapse everything before the first one-size group to the
    // left and to the right of the last one. In the middle, the only thing we
    // could do is potentially fold in half, which requires us having a
    // palindrome.
    //
    // Once we know the row set and column set are both foldable,
    // we only need to check that the given marked cells form exactly
    // the Cartesian product of these two sets (a complete rectangle
    // with no holes and no extra cells).

    vector<int> rows(k), cols(k);
    for(int i = 0; i < k; i++) {
        rows[i] = pts[i].first;
        cols[i] = pts[i].second;
    }

    sort(rows.begin(), rows.end());
    rows.erase(unique(rows.begin(), rows.end()), rows.end());
    sort(cols.begin(), cols.end());
    cols.erase(unique(cols.begin(), cols.end()), cols.end());

    if(!foldable_1d(rows, n) || !foldable_1d(cols, m)) {
        cout << "NO\n";
        return;
    }

    sort(pts.begin(), pts.end());
    if(!is_full_grid(pts, cols)) {
        cout << "NO\n";
        return;
    }

    cout << "YES\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python Solution

```python
import sys


def foldable_1d(v, lim):
    """
    Checks whether marked positions v in a 1D strip of length lim
    can be folded into one stack without including unmarked positions.

    v must be sorted and contain unique positions.
    """

    s = len(v)  # Number of marked positions.

    # Zero or one marked position is always foldable.
    if s < 2:
        return True

    # Consecutive marked positions must have odd distance.
    # If the distance is even, the structure cannot be folded correctly.
    for i in range(1, s):
        if (v[i] - v[i - 1]) % 2 == 0:
            return False

    # low and high delimit the still-relevant middle part of v.
    low = 0
    high = s

    # Current effective left and right borders of the strip.
    left_border = 1
    right_border = lim

    # Remove consecutive marked cells touching the left border.
    while low < high and v[low] == left_border:
        low += 1
        left_border += 1

    # Remove consecutive marked cells touching the right border.
    while low < high and v[high - 1] == right_border:
        high -= 1
        right_border -= 1

    # seq stores alternating:
    # run length of consecutive marked cells,
    # gap between this run and the next run.
    seq = []

    i = low

    # Split the remaining marked positions into consecutive runs.
    while i < high:
        j = i

        # Find the end of the current consecutive marked run.
        while j + 1 < high and v[j + 1] == v[j] + 1:
            j += 1

        # Length of current consecutive marked run.
        run_len = j - i + 1

        # Internal runs longer than one must have even length.
        if run_len > 1 and run_len % 2 == 1:
            return False

        # Store current run length.
        seq.append(run_len)

        # If another run follows, store the distance to the next run.
        if j + 1 < high:
            seq.append(v[j + 1] - v[j])

        # Move to the next run.
        i = j + 1

    # prev stores the index in seq of the previous isolated single run.
    prev = -1

    # Run lengths are located at even indices in seq.
    for idx in range(0, len(seq), 2):
        # Only isolated single-cell runs require palindrome checks.
        if seq[idx] != 1:
            continue

        # If there was a previous isolated run, check symmetry between them.
        if prev >= 0:
            l = prev + 1
            r = idx - 1

            # The pattern between two isolated marks must be palindromic.
            while l < r:
                if seq[l] != seq[r]:
                    return False
                l += 1
                r -= 1

        # Remember this isolated single run.
        prev = idx

    # All checks passed.
    return True


def is_full_grid(cells, cols):
    """
    Checks whether sorted marked cells form exactly R x cols,
    where R is the set of distinct rows appearing in cells.

    cells must be sorted lexicographically by row and column.
    cols must be sorted unique columns.
    """

    n_cells = len(cells)  # Number of marked cells.
    n_cols = len(cols)    # Number of distinct marked columns.

    # No marked cells: trivially okay.
    if n_cells == 0:
        return True

    # If there are marked cells but no columns, impossible.
    # This is mostly defensive; with valid input this should not happen.
    if n_cols == 0:
        return False

    # A full grid must contain the same number of columns in every row.
    if n_cells % n_cols != 0:
        return False

    # Number of rows in the supposed full product.
    n_rows = n_cells // n_cols

    # Check each row block.
    for row_idx in range(n_rows):
        # First cell of this block determines the expected row value.
        expected_row = cells[row_idx * n_cols][0]

        # Every column must appear exactly once in this row.
        for col_idx in range(n_cols):
            cell = cells[row_idx * n_cols + col_idx]

            # The row and column must match the expected Cartesian product.
            if cell[0] != expected_row or cell[1] != cols[col_idx]:
                return False

    # All rows contain exactly all columns.
    return True


def solve():
    # Read all integers from standard input.
    data = list(map(int, sys.stdin.buffer.read().split()))

    # If input is empty, do nothing.
    if not data:
        return

    # First three integers are n, m, k.
    n, m, k = data[0], data[1], data[2]

    # Remaining data contains k pairs.
    pts = []

    index = 3

    # Read marked cells.
    for _ in range(k):
        x = data[index]
        y = data[index + 1]
        index += 2
        pts.append((x, y))

    # Extract distinct marked rows and columns.
    rows = sorted(set(x for x, y in pts))
    cols = sorted(set(y for x, y in pts))

    # Row set and column set must be independently foldable.
    if not foldable_1d(rows, n) or not foldable_1d(cols, m):
        print("NO")
        return

    # Sort cells by row, then column.
    pts.sort()

    # Marked cells must form the complete Cartesian product rows x cols.
    if not is_full_grid(pts, cols):
        print("NO")
        return

    # All conditions passed.
    print("YES")


if __name__ == "__main__":
    solve()
```

---

## 5. Compressed Editorial

Folding rows and columns are independent operations. Let `R` be all marked rows and `C` be all marked columns. For all marked cells to end in one stack, all rows in `R` must be foldable together, all columns in `C` must be foldable together, and every cell in `R × C` must be marked; otherwise an unmarked cell would also appear in the final marked stack.

For a 1D set of marked positions:

1. Consecutive marked positions must differ by an odd number.
2. Consecutive marked runs touching the left or right border can be ignored.
3. Remaining internal marked runs of length greater than `1` must have even length.
4. Between consecutive isolated single marked cells, the alternating sequence of run lengths and gaps must be palindromic.

Check these conditions for rows and columns. Then sort marked cells and verify they form the full Cartesian product of distinct rows and distinct columns.

Complexity:

```text
O(k log k)
```
