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

```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;
}
```

---

## 5. Python Implementation

```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()
```
