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

262. Symbol Recognition
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Consider a monochrome computer monitor with N x M pixels resolution. It can display K symbols. Symbol is a non-empty set of black pixels on the screen. You are to write a program, that computes minimal possible amount of pixels, that are enough to recognize a symbol.

Input
First line of input contains integers N, M, K (1 <= N, M <= 10, 2 <= K <= 6). K blocks follow, separated by empty lines. Each block consists of N rows of M characters. It's a symbols representation on the N x M screen. `1' denotes black pixel, `0' denotes white pixel. You may assume that symbols are unique.

Output
Print on the first line of output the minimal possible amount of pixels that enough to recognize symbol. I.e. you have to find set of pixels that has different color in each pair of symbols. If there are several sets with equal amount of pixels, output any of them. Then print N lines M characters each. `1' denotes that corresponding pixel is in your set. `0' denotes that corresponding pixel is not in your set.

Sample test(s)

Input
2 4 3
0000
0001

1000
0001

1111
1001

Output
2
1000
1000

Note
In this example output set consists of two most left pixels. They are both white in first symbol; black and white in second symbol; both black in third symbol. So, it's possible to recognize each symbol using this set of pixels.
Author:	Andrew V. Lazarev
Resource:	Saratov SU Contest: Golden Fall 2004
Date:	October 2, 2004

<|response|>
## 1) Abridged problem statement (concise)

You are given **K** distinct monochrome symbols (2 ≤ K ≤ 6), each drawn on an **N×M** grid (1 ≤ N,M ≤ 10) using `0/1`.  
Choose a **minimum-size set of pixel positions** such that **every pair of symbols differs on at least one chosen pixel**.  

Output:
1) the minimum number of chosen pixels  
2) an **N×M mask** (`1` = chosen pixel, `0` = not chosen) achieving it.

---

## 2) Key observations

1. **What it means to “recognize” a symbol**  
   A set of pixels \(S\) is sufficient iff for every pair of different symbols \((a,b)\), there exists a pixel \(p \in S\) with different colors:
   \[
   symbol[a][p] \ne symbol[b][p]
   \]

2. **The number of symbol pairs is tiny**  
   With \(K \le 6\), the number of unordered pairs is:
   \[
   P=\binom{K}{2}\le 15
   \]
   So we can represent “which pairs are already distinguished” using a **bitmask** of length \(P\).

3. **Each pixel distinguishes a fixed subset of symbol-pairs**  
   For a given pixel position \(p\), it either differs or not for each pair \((a,b)\).  
   Precompute a bitmask `pixel_mask[p]` telling which pairs are distinguished by selecting pixel \(p\).

4. **This becomes a minimum set cover on only 15 elements**  
   We want the minimum number of pixels whose OR of masks covers all \(P\) pairs.  
   Solve via standard **0/1 DP over pixels and masks**:  
   \(T=N\cdot M \le 100\), states \(T \cdot 2^P \le 100 \cdot 2^{15}\), feasible.

---

## 3) Full solution approach

### Step A: Read and flatten symbols
Flatten each symbol’s grid into a 1D array of length \(T=N\cdot M\) in row-major order.

### Step B: Enumerate symbol pairs
Create a list `pairs = [(0,1), (0,2), ...]` of size \(P\).

### Step C: Precompute `pixel_mask` for each pixel
For each pixel index `p` in `[0..T-1]`:
- Initialize `mask = 0`
- For each pair index `i` corresponding to `(a,b)`:
  - if `symbols[a][p] != symbols[b][p]`, set bit `i` in `mask`

So selecting pixel `p` contributes `pixel_mask[p]`.

### Step D: DP to minimize selected pixels
Let:
- `full_mask = (1<<P) - 1` (all pairs distinguished)
- `dp[pos][mask]` = minimum selected pixels considering first `pos` pixels, achieving distinguished-pairs state `mask`

Transitions for pixel `pos` (0-indexed, transitioning to `pos+1`):
1. **Skip** pixel: `dp[pos+1][mask] = min(dp[pos+1][mask], dp[pos][mask])`
2. **Take** pixel:  
   `new_mask = mask | pixel_mask[pos]`  
   `dp[pos+1][new_mask] = min(dp[pos+1][new_mask], dp[pos][mask] + 1)`

### Step E: Reconstruct an optimal chosen set
Store parent information (previous mask) to backtrack:
- If the mask changes from `prev_mask` to `mask`, the pixel was taken; otherwise skipped.

### Step F: Output
Print:
- `dp[T][full_mask]`
- the `N×M` chosen-pixel mask

---

## 4) C++ implementation (detailed comments)

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

/*
  p262 - Symbol Recognition

  Idea:
  - There are K<=6 symbols -> number of pairs P=C(K,2)<=15.
  - We need a minimum set of pixels such that for every pair of symbols,
    at least one chosen pixel differs between them.
  - Treat each pair as an "item" to cover. Each pixel covers a subset of pairs.
  - DP over pixels and bitmask of covered pairs.
*/

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

    int N, M, K;
    cin >> N >> M >> K;
    int T = N * M; // total pixels

    // Read K symbols, flatten each into a vector<int> of length T.
    vector<vector<int>> sym(K, vector<int>(T, 0));

    for (int s = 0; s < K; s++) {
        for (int i = 0; i < N; i++) {
            string row;
            cin >> row; // operator>> skips whitespace, so empty lines are fine
            for (int j = 0; j < M; j++) {
                sym[s][i * M + j] = (row[j] == '1') ? 1 : 0;
            }
        }
    }

    // Enumerate all unordered symbol pairs (a<b).
    vector<pair<int,int>> pair_list;
    for (int a = 0; a < K; a++)
        for (int b = a + 1; b < K; b++)
            pair_list.push_back({a, b});

    int P = (int)pair_list.size();        // <= 15
    int full_mask = (1 << P) - 1;

    // For each pixel position p, compute which pairs it distinguishes.
    vector<int> pixel_mask(T, 0);
    for (int p = 0; p < T; p++) {
        int mask = 0;
        for (int i = 0; i < P; i++) {
            auto [a, b] = pair_list[i];
            if (sym[a][p] != sym[b][p]) mask |= (1 << i);
        }
        pixel_mask[p] = mask;
    }

    // DP: dp[pos][mask] = min chosen pixels using first pos pixels to achieve mask.
    const int INF = T + 1;
    vector<vector<int>> dp(T + 1, vector<int>(full_mask + 1, INF));

    // For reconstruction:
    // prev_mask[pos][mask] = mask value at pos-1 that led to dp[pos][mask]
    vector<vector<int>> prev_mask(T + 1, vector<int>(full_mask + 1, -1));

    dp[0][0] = 0;
    prev_mask[0][0] = 0;

    for (int pos = 0; pos < T; pos++) {
        for (int mask = 0; mask <= full_mask; mask++) {
            if (dp[pos][mask] == INF) continue;

            // Option 1: skip this pixel
            if (dp[pos + 1][mask] > dp[pos][mask]) {
                dp[pos + 1][mask] = dp[pos][mask];
                prev_mask[pos + 1][mask] = mask;
            }

            // Option 2: take this pixel
            int new_mask = mask | pixel_mask[pos];
            if (dp[pos + 1][new_mask] > dp[pos][mask] + 1) {
                dp[pos + 1][new_mask] = dp[pos][mask] + 1;
                prev_mask[pos + 1][new_mask] = mask;
            }
        }
    }

    // Reconstruct chosen pixels from (T, full_mask).
    vector<int> chosen(T, 0);
    int cur_mask = full_mask;
    for (int pos = T; pos >= 1; pos--) {
        int pm = prev_mask[pos][cur_mask]; // previous mask before processing pixel pos-1
        // If mask changed, that means we took pixel pos-1 (skipping keeps mask same).
        if (pm != cur_mask) chosen[pos - 1] = 1;
        cur_mask = pm;
    }

    // Output answer
    cout << dp[T][full_mask] << "\n";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << (chosen[i * M + j] ? '1' : '0');
        }
        cout << "\n";
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def solve() -> None:
    # Read all tokens; this naturally ignores empty lines.
    data = sys.stdin.read().split()
    it = iter(data)

    N = int(next(it))
    M = int(next(it))
    K = int(next(it))
    T = N * M

    # Read K symbols, each with N rows of length M, flattened into length T arrays.
    symbols = []
    for _ in range(K):
        flat = []
        for _ in range(N):
            row = next(it)
            flat.extend(1 if c == '1' else 0 for c in row)
        symbols.append(flat)

    # Build list of all unordered symbol pairs.
    pair_list = []
    for a in range(K):
        for b in range(a + 1, K):
            pair_list.append((a, b))

    P = len(pair_list)                # <= 15
    full_mask = (1 << P) - 1

    # pixel_mask[p] = bitmask of pairs distinguished by choosing pixel p.
    pixel_mask = [0] * T
    for p in range(T):
        mask = 0
        for i, (a, b) in enumerate(pair_list):
            if symbols[a][p] != symbols[b][p]:
                mask |= (1 << i)
        pixel_mask[p] = mask

    INF = T + 1

    # dp[pos][mask] = minimal chosen pixels using first pos pixels to get 'mask'
    dp = [[INF] * (full_mask + 1) for _ in range(T + 1)]
    prev = [[-1] * (full_mask + 1) for _ in range(T + 1)]

    dp[0][0] = 0
    prev[0][0] = 0

    for pos in range(T):
        for mask in range(full_mask + 1):
            cur = dp[pos][mask]
            if cur == INF:
                continue

            # Skip pixel pos
            if dp[pos + 1][mask] > cur:
                dp[pos + 1][mask] = cur
                prev[pos + 1][mask] = mask

            # Take pixel pos
            new_mask = mask | pixel_mask[pos]
            if dp[pos + 1][new_mask] > cur + 1:
                dp[pos + 1][new_mask] = cur + 1
                prev[pos + 1][new_mask] = mask

    # Reconstruct chosen pixels by walking backward from (T, full_mask)
    chosen = [0] * T
    mask = full_mask
    for pos in range(T, 0, -1):
        pm = prev[pos][mask]
        # If mask changed, pixel pos-1 was taken.
        if pm != mask:
            chosen[pos - 1] = 1
        mask = pm

    # Output
    out_lines = [str(dp[T][full_mask])]
    for i in range(N):
        row = chosen[i * M : (i + 1) * M]
        out_lines.append("".join('1' if x else '0' for x in row))

    sys.stdout.write("\n".join(out_lines))

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

These implementations follow the same core plan: encode symbol-pairs as bits, precompute each pixel’s contribution, run a minimal 0/1 DP, then backtrack to print one optimal mask.