<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

391. Mr. X
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Mr. X (he is famous for his 13 feats) has a piece of chequered paper. Some of the cells are marked with a special sign. He can fold the piece of paper anywhere along a line between two successive rows or columns. After the fold is performed, he considers a folded paper as a new piece of paper, so he may continue the folding process. Now Mr. X wonders whether it is possible to combine all the marked cells together performing some sequence of folds (marked cells must be all one under another, and no unmarked cell must be under or above the marked cells). So he asks for your help.
Input
The first line of the input file contains integers n, m and k — number of rows, columns and marked cells correspondingly (). Each of the following k lines describes one marked cell and contains two integer numbers xi and yi that are row and column indices (1 ≤ xi ≤ n, 1 ≤ yi ≤ m).
Output
If it is possible for Mr. X to combine all the marked cells together, output "YES", otherwise output "NO" (quotes for clarity).
Example(s)
sample input
sample output
4 4 4
1 1 
4 1
1 4
4 4
YES

sample input
sample output
4 4 3
1 1 
4 1
1 4
NO

<|response|>
## 1. Abridged Problem Statement

You are given an `n × m` grid with `k` marked cells.

You may repeatedly fold the paper along a line between two adjacent rows or between two adjacent columns. After every fold, the folded paper becomes the new paper.

Determine whether it is possible to fold the paper so that:

- all marked cells are exactly on top of each other;
- no unmarked cell is in the same final stack as the marked cells.

Print `"YES"` if possible, otherwise print `"NO"`.

---

## 2. Key Observations

### Observation 1: Rows and columns are independent

A horizontal fold only changes row positions.  
A vertical fold only changes column positions.

Therefore, we can treat the problem as two independent 1D folding problems:

- Can all marked rows be folded into one row?
- Can all marked columns be folded into one column?

Let:

- `R` = set of rows containing at least one marked cell;
- `C` = set of columns containing at least one marked cell.

Both `R` and `C` must be foldable independently.

---

### Observation 2: Marked cells must form a full Cartesian product

Even if all marked rows and marked columns can be merged, there is another condition.

If rows in `R` are merged together and columns in `C` are merged together, then every cell in:

```text
R × C
```

will end up in the final stack.

So every cell `(r, c)` where `r ∈ R` and `c ∈ C` must be marked.

Example:

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

Here:

```text
R = {1, 4}
C = {1, 4}
```

All cells in `R × C` are marked, so this condition is satisfied.

But for:

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

Cell `(4, 4)` is missing, so an unmarked cell would end up in the marked stack. Hence the answer is `"NO"`.

---

### Observation 3: 1D folding properties

Consider a 1D strip of length `lim` with marked positions.

A fold is always made between two adjacent cells, so the fold line is at a half-integer position.

If two cells become stacked by reflection, their positions have an odd difference.

Therefore, for sorted marked positions `v`, every consecutive difference must be odd:

```text
v[i] - v[i - 1] must be odd
```

If any such difference is even, folding is impossible.

---

### Observation 4: Border runs can be removed

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

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

then they can be folded inward safely.

Similarly, a consecutive marked run ending at the right border can also be safely removed.

So in the 1D check, we first remove consecutive marked positions touching either border.

---

### Observation 5: Internal runs

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

For example:

```text
4 5 8 12 13
```

has runs:

```text
[4, 5], [8], [12, 13]
```

Any internal run of length greater than `1` must have even length.

Why?

An even-length run can be folded around its middle line, which lies between two cells.  
An odd-length internal run would have its center on a cell, which is impossible because folds are only allowed between cells.

So:

```text
internal run length > 1 must be even
```

---

### Observation 6: Isolated single marked cells require symmetry

Internal runs of length `1` are special.

If two isolated marked cells need to be merged, the fold line must be exactly between them. That means the whole pattern between them must be symmetric.

The algorithm stores an alternating sequence:

```text
run length, gap, run length, gap, run length, ...
```

Between every pair of consecutive single-cell runs, the sequence must be a palindrome.

---

## 3. Full Solution Approach

### Step 1: Read input

Store all marked cells as pairs:

```cpp
(row, column)
```

---

### Step 2: Extract marked rows and columns

Create:

```text
rows = sorted unique row indices
cols = sorted unique column indices
```

---

### Step 3: Check 1D foldability

Use a helper function:

```text
foldable_1d(v, lim)
```

where:

- `v` is a sorted unique list of marked positions;
- `lim` is the strip length.

The function works as follows:

1. If there are zero or one marked positions, return `true`.

2. Check that every consecutive distance is odd.

3. Remove consecutive marked positions touching the left border.

4. Remove consecutive marked positions touching the right border.

5. Split the remaining positions into consecutive runs.

6. Every internal run of length greater than `1` must have even length.

7. Build an alternating sequence of:

   ```text
   run length, gap, run length, gap, ...
   ```

8. For every pair of consecutive isolated single-cell runs, check that the sequence between them is palindromic.

If all checks pass, return `true`.

---

### Step 4: Check the full Cartesian product condition

The marked cells must be exactly:

```text
rows × cols
```

So:

```text
number of marked cells must equal rows.size() * cols.size()
```

Then, after sorting the cells lexicographically, we check that they appear in this exact order:

```text
(rows[0], cols[0])
(rows[0], cols[1])
...
(rows[1], cols[0])
(rows[1], cols[1])
...
```

If not, output `"NO"`.

---

### Step 5: Final answer

Output `"YES"` only if:

```text
foldable_1d(rows, n) is true
foldable_1d(cols, m) is true
marked cells form rows × cols
```

---

### Complexity

Sorting dominates the solution.

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

---

## 4. C++ Implementation with Detailed Comments

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
    Checks whether marked positions v in a 1D strip of length lim
    can be folded into one stack without including unmarked cells.

    v must be sorted and contain unique values.
*/
bool foldable_1d(const vector<int>& v, int lim) {
    int s = (int)v.size();

    // Zero or one marked position is always foldable.
    if (s < 2) {
        return true;
    }

    /*
        If two marked positions are eventually stacked together,
        their distance must be odd because folding is done around
        a line between two cells.

        Hence every consecutive difference must be odd.
    */
    for (int i = 1; i < s; i++) {
        if ((v[i] - v[i - 1]) % 2 == 0) {
            return false;
        }
    }

    int low = 0;
    int high = s;

    int left_border = 1;
    int right_border = lim;

    /*
        Remove a consecutive marked run touching the left border.

        Example:
            1 2 3 ...
        Such cells can be folded inward safely.
    */
    while (low < high && v[low] == left_border) {
        low++;
        left_border++;
    }

    /*
        Remove a consecutive marked run touching the right border.

        Example:
            ... lim-2 lim-1 lim
    */
    while (low < high && v[high - 1] == right_border) {
        high--;
        right_border--;
    }

    /*
        seq stores alternating values:

            run length, gap, run length, gap, ...

        Here "gap" is stored as the distance between the last marked
        cell of one run and the first marked cell of the next run.
    */
    vector<int> seq;

    for (int i = low; i < high; ) {
        int j = i;

        // Find the end of the current consecutive marked run.
        while (j + 1 < high && v[j + 1] == v[j] + 1) {
            j++;
        }

        int run_len = j - i + 1;

        /*
            Any internal marked run of length > 1 must have even length.
            An odd-length internal run cannot be folded around a line
            between two cells.
        */
        if (run_len > 1 && (run_len % 2 == 1)) {
            return false;
        }

        // Store the current run length.
        seq.push_back(run_len);

        // If another run exists, store the distance to it.
        if (j + 1 < high) {
            seq.push_back(v[j + 1] - v[j]);
        }

        i = j + 1;
    }

    /*
        Isolated single-cell runs are the difficult case.

        Between every pair of consecutive isolated single-cell runs,
        the run-gap pattern must be symmetric, i.e. palindromic.
    */
    int prev_single = -1;

    // Run lengths are at even indices: 0, 2, 4, ...
    for (int idx = 0; idx < (int)seq.size(); idx += 2) {
        if (seq[idx] != 1) {
            continue;
        }

        if (prev_single != -1) {
            int l = prev_single + 1;
            int r = idx - 1;

            while (l < r) {
                if (seq[l] != seq[r]) {
                    return false;
                }
                l++;
                r--;
            }
        }

        prev_single = idx;
    }

    return true;
}

/*
    Checks whether the sorted marked cells form exactly rows x cols.

    rows and cols must be sorted unique arrays.
    cells must be sorted lexicographically.
*/
bool is_full_grid(const vector<pair<int, int>>& cells,
                  const vector<int>& rows,
                  const vector<int>& cols) {
    long long expected = 1LL * rows.size() * cols.size();

    if (expected != (long long)cells.size()) {
        return false;
    }

    int index = 0;

    for (int r : rows) {
        for (int c : cols) {
            if (cells[index] != make_pair(r, c)) {
                return false;
            }
            index++;
        }
    }

    return true;
}

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

    int n, m, k;
    cin >> n >> m >> k;

    vector<pair<int, int>> cells(k);

    for (int i = 0; i < k; i++) {
        cin >> cells[i].first >> cells[i].second;
    }

    // Extract all marked rows and columns.
    vector<int> rows;
    vector<int> cols;

    rows.reserve(k);
    cols.reserve(k);

    for (auto [x, y] : cells) {
        rows.push_back(x);
        cols.push_back(y);
    }

    // Sort and remove duplicates from rows.
    sort(rows.begin(), rows.end());
    rows.erase(unique(rows.begin(), rows.end()), rows.end());

    // Sort and remove duplicates from columns.
    sort(cols.begin(), cols.end());
    cols.erase(unique(cols.begin(), cols.end()), cols.end());

    // Rows and columns must be independently foldable.
    if (!foldable_1d(rows, n) || !foldable_1d(cols, m)) {
        cout << "NO\n";
        return 0;
    }

    // Check that the marked cells form the full Cartesian product rows x cols.
    sort(cells.begin(), cells.end());

    if (!is_full_grid(cells, rows, cols)) {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";
    return 0;
}
```

---

## 5. Python Implementation with Detailed Comments

```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 cells.

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

    s = len(v)

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

    # Every consecutive distance between marked positions must be odd.
    for i in range(1, s):
        if (v[i] - v[i - 1]) % 2 == 0:
            return False

    low = 0
    high = s

    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 values:

        run length, gap, run length, gap, ...

    The gap is stored as the distance between the last marked cell
    of the current run and the first marked cell of the next run.
    """
    seq = []

    i = low

    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

        run_len = j - i + 1

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

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

        # Store the distance to the next run, if it exists.
        if j + 1 < high:
            seq.append(v[j + 1] - v[j])

        i = j + 1

    """
    For every pair of consecutive isolated single-cell runs,
    the pattern between them must be palindromic.
    """
    prev_single = -1

    # Run lengths are located at even indices: 0, 2, 4, ...
    for idx in range(0, len(seq), 2):
        if seq[idx] != 1:
            continue

        if prev_single != -1:
            l = prev_single + 1
            r = idx - 1

            while l < r:
                if seq[l] != seq[r]:
                    return False
                l += 1
                r -= 1

        prev_single = idx

    return True


def is_full_grid(cells, rows, cols):
    """
    Checks whether marked cells form exactly rows x cols.

    cells must be sorted lexicographically.
    rows and cols must be sorted unique lists.
    """

    expected = len(rows) * len(cols)

    if expected != len(cells):
        return False

    index = 0

    for r in rows:
        for c in cols:
            if cells[index] != (r, c):
                return False
            index += 1

    return True


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))

    if not data:
        return

    n, m, k = data[0], data[1], data[2]

    cells = []
    ptr = 3

    for _ in range(k):
        x = data[ptr]
        y = data[ptr + 1]
        ptr += 2
        cells.append((x, y))

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

    # Rows and columns must be independently foldable.
    if not foldable_1d(rows, n):
        print("NO")
        return

    if not foldable_1d(cols, m):
        print("NO")
        return

    # Marked cells must form exactly rows x cols.
    cells.sort()

    if not is_full_grid(cells, rows, cols):
        print("NO")
        return

    print("YES")


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