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

433. Japhshan and Ramshut
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Today Japhshan and Ramshut are laying the pavement in front of Mrs. Kotchak's house. Pavement has the form of a rectangle of size M x N. Our workers have an infinite number of bricks of sizes 1 x L1, 1 x L2,..., 1 x LK at their disposal (the bricks were laying around unused at the nearby construction site). Your task is to find a way to compose a pavement out of these bricks (without holes and overlaps) or to determine that it is impossible.

Input
The first line of input contains three integer numbers N, M and K (, 2 ≤ M + N ≤ 20, 1 ≤ K ≤ 5). Second line contains K numbers — lengths of bricks. All brick lengths are positive and do not exceed 1000.

Output
If it is possible to compose the pavement, output "YES" (without quotes) on the first line, then N lines of M lowercase Latin letters describing the composition. Two adjacent letters should be the same if they are related to the same brick, and different otherwise. If the composition is impossible, output "NO" (without quotes). If there is more than one way to compose the pavement, output any.

Example(s)
sample input
sample output
5 5 2
3 4
YES
aaaab
ccccb
adddb
acccc
abbbb

<|response|>
## 1. Abridged problem statement

Given an `N × M` rectangle and infinitely many bricks of sizes

```text
1 × L1, 1 × L2, ..., 1 × LK
```

bricks may be rotated, so they can also be placed as `Li × 1`.

We need to tile the whole rectangle without holes or overlaps.

If impossible, print:

```text
NO
```

Otherwise print:

```text
YES
```

and an `N × M` grid of lowercase letters such that:

- cells of the same brick have the same letter;
- adjacent cells belonging to different bricks have different letters.

Constraints are small in dimensions:

```text
2 ≤ N + M ≤ 20
1 ≤ K ≤ 5
Li ≤ 1000
```

---

## 2. Key observations

### Observation 1: Think about orientations first

Instead of immediately placing individual bricks, decide only whether each cell belongs to a horizontal or vertical brick.

Let:

- `1` mean this cell belongs to a horizontal brick;
- `0` mean this cell belongs to a vertical brick.

Then:

- every maximal consecutive run of `1`s in a row must have length expressible as a sum of allowed brick lengths;
- every maximal consecutive run of `0`s in a column must have length expressible as a sum of allowed brick lengths.

For example, if available lengths are `{3, 4}`, then a horizontal run of length `7` is valid because:

```text
7 = 3 + 4
```

Once such an orientation matrix is found, every valid run can be split into actual bricks.

---

### Observation 2: Representable lengths can be precomputed

We only care about lengths up to:

```cpp
max(N, M)
```

Let:

```cpp
rep[x] = true
```

if length `x` can be represented as a sum of allowed brick lengths.

This is standard unbounded knapsack / coin change DP.

We also store a parent value `par[x]`, one brick length used in the representation of `x`, so that later we can reconstruct actual bricks.

---

### Observation 3: Work with the smaller side as height

Let:

```cpp
h = min(N, M)
w = max(N, M)
```

We process the rectangle column by column. Since the height is the smaller dimension, a column can be represented by a bitmask of at most `10` bits because:

```text
N + M ≤ 20
```

So mask enumeration is feasible.

---

### Observation 4: Column masks handle vertical constraints

A column mask is valid if every maximal run of zero bits has representable length.

Example:

```text
mask bits: 1 0 0 1 0
```

The zero-runs have lengths `2` and `1`. Both must be representable.

If a column mask is valid, then all vertical pieces inside this column can eventually be split into real bricks.

---

### Observation 5: DP over columns handles horizontal constraints

While sweeping columns left to right, keep for each row the length of the current open horizontal run.

Example state:

```text
runs = [0, 3, 1, 0]
```

means:

- row `0`: no currently open horizontal run;
- row `1`: current horizontal run has length `3`;
- row `2`: current horizontal run has length `1`;
- row `3`: no currently open horizontal run.

When adding a column mask:

- if bit is `1`, the horizontal run grows by `1`;
- if bit is `0`, the horizontal run ends, so its length must be representable.

After all columns are processed, all still-open horizontal runs must also be representable.

---

### Observation 6: Compress DP states using periodicity

Naively, each row's open run length can be from `0` to `w`, so the number of states can be large.

But representable lengths are eventually periodic modulo the gcd of usable brick lengths.

Let:

```cpp
g = gcd(all brick lengths not exceeding max(N, M))
```

For sufficiently large values, whether length `x` is representable depends only on `x mod g`.

So we canonicalize run lengths before using them as DP keys.

---

### Observation 7: Coloring bricks

After constructing actual bricks, we need assign lowercase letters.

Build an adjacency graph:

- each brick is a vertex;
- two bricks are adjacent if they share an edge.

This graph is planar. A planar graph is 6-colorable by the degeneracy argument. We can use smallest-last ordering and greedy coloring. This will use at most 6 colors, safely within lowercase letters.

---

## 3. Full solution approach

### Step 1: Compute representable lengths

Use unbounded coin DP:

```cpp
rep[0] = true;

for s = 1..max(N, M):
    for len in lengths:
        if s >= len and rep[s - len]:
            rep[s] = true
            par[s] = len
```

`par[s]` allows reconstructing one decomposition of `s`.

---

### Step 2: Normalize dimensions

Internally work with:

```cpp
h = min(N, M)
w = max(N, M)
```

If `N > M`, we solve the transposed rectangle and transpose the final output back.

---

### Step 3: Easy cases

If `w` is representable, tile every row horizontally.

If `w` is not representable but `h` is representable, tile every column vertically.

Otherwise, we need a mixed orientation matrix.

---

### Step 4: Precompute valid column masks

For every mask from `0` to `(1 << h) - 1`, check every zero-run.

If all zero-run lengths are representable, keep this mask.

---

### Step 5: DP over columns

State:

```cpp
runs[0..h-1]
```

where `runs[r]` is the length of the currently open horizontal run in row `r`.

Transition with a valid column mask:

- bit `1`: `runs[r] += 1`;
- bit `0`: close current horizontal run, requiring it to be representable.

Store parent pointers to reconstruct the chosen masks.

---

### Step 6: Reconstruct the orientation matrix

If an accepting final state is found, walk parent pointers backward.

This gives every column mask, hence the whole `0/1` orientation matrix.

---

### Step 7: Split runs into bricks

For every horizontal run of `1`s, use `par[]` to split it into brick lengths.

For every vertical run of `0`s, do the same.

Assign each brick a unique integer ID.

---

### Step 8: Build adjacency graph and color bricks

For every pair of adjacent cells, if they belong to different bricks, add an edge between those brick IDs.

Then color the graph using smallest-last greedy coloring.

Finally, output the color of the brick covering each cell.

---

## 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<int> lengths;

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

void solve() {
    // The key idea is to stop thinking about individual bricks and instead
    // decide, for each cell, only the orientation of the brick covering it:
    // give the cell a 1 if it belongs to a horizontal brick and a 0 if it
    // belongs to a vertical one. Walk along a row: a maximal run of 1's is a
    // strip that is covered purely by horizontal bricks laid end to end, so
    // the run length must be a sum of brick lengths. Walk down a column: a
    // maximal run of 0's is covered purely by vertical bricks, so its length
    // must also be a sum of brick lengths. Conversely, any 0/1 matrix whose
    // horizontal 1-runs and vertical 0-runs all have such lengths can be cut
    // straight into bricks. So a tiling exists exactly when this orientation
    // matrix exists, and our whole job is to build one.
    //
    // Call a length "representable" if it is a non-negative combination of the
    // brick lengths. rep[s] is the coin-reachability of s computed bottom-up,
    // and par[s] remembers one brick length used to reach s, which lets us
    // later chop a run of representable length back into concrete bricks.
    //
    // Two cases are immediate. If the width is representable, every row on its
    // own is a horizontal strip of a representable length, so make the whole
    // matrix 1's (all bricks horizontal). If the width is not representable but
    // the height is, every column is a vertical strip, so leave the matrix all
    // 0's (all bricks vertical) - that is exactly the do-nothing branch below.
    //
    // The interesting case is when neither dimension is representable. We build
    // the orientation matrix one full column at a time, left to right. Write a
    // column as a bitmask x in {0,1}^h, where bit r is the orientation of cell
    // (r, current column): 1 horizontal, 0 vertical.
    //
    // The vertical constraint lives entirely inside one column and never
    // couples to its neighbours: x is "legal" iff every maximal run of 0-bits
    // in x has representable length. These legal masks are few here (if many
    // run lengths were representable the height itself would be), so we list
    // the whole set C = { legal x } up front and only ever place columns from
    // C. That leaves just the horizontal constraint, which does couple columns,
    // for the sweep to enforce. The DP is:
    //
    //   state    run[0..h-1], where run[r] is the length of the horizontal
    //            1-run in row r that is still open at the current column - i.e.
    //            the number of consecutive 1-bits in row r ending here, or 0 if
    //            the last placed column had a 0 in row r.
    //
    //   base     before any column is placed the state is run = (0, ..., 0).
    //
    //   step     to extend state run by a column x in C, look at each row r:
    //              x_r = 1  -> the run grows:      run'[r] = run[r] + 1
    //              x_r = 0  -> the run ends here, which is legal only if its
    //                          length is representable (rep[run[r]], or run[r]
    //                          was already 0); then run'[r] = 0.
    //            if any row's closing length is not representable, x is
    //            rejected from this state.
    //
    //   accept   after all w columns, a state is accepting iff every row's
    //            still-open run is representable (rep[run[r]] or run[r] = 0) -
    //            this is the right-border closing of the last bricks.
    //
    // A column extends a state iff a tiling-legal orientation matrix can have
    // those run lengths at that boundary, so reaching an accepting state after
    // w columns is exactly a valid matrix. Each DP node stores its predecessor
    // and the mask x that produced it, so from an accepting state we walk the
    // chain back to read off the column masks.
    //
    // On the number of states: each run[r] ranges over [0, w], so the naive
    // bound is (w + 1)^h distinct vectors, far too many to enumerate. What
    // saves us is that we only keep states that are prefixes of genuine
    // tilings - a run may stay open only while it can still close at a
    // representable length, so a column that strands some row at a length that
    // can never become representable is rejected on the spot and never spawns a
    // state. That decomposability requirement is what does the real pruning. On
    // top of it we fold equivalent run lengths together before using a state as
    // a dedup key: all that a run length L means for the future is the sequence
    // rep[L], rep[L + 1], ..., which is eventually periodic with period g (the
    // gcd of the lengths that fit), so canon[] maps L to a representative of its
    // class. For a dense set such as a single length 2 this collapses runs to
    // their parity; for a sparse set it changes nothing. Together these keep
    // the reachable states in the low thousands, so the sweep is fast in
    // practice.
    //
    // The board is always handled with its shorter side as the height h (and
    // the answer transposed back at the end when we flipped it), which keeps
    // both the 2^h mask enumeration and the per-row state vector small. Once
    // the orientation matrix is fixed, par[] cuts every horizontal and vertical
    // run into bricks with distinct ids, and the bricks are finally given
    // letters by a smallest-last greedy coloring. The brick adjacency graph is
    // planar, so this never needs more than six of the available letters.

    int dim = max(n, m);
    vector<char> rep(dim + 1, false);
    vector<int> par(dim + 1, -1);
    rep[0] = true;
    for(int s = 1; s <= dim; s++) {
        for(int len: lengths) {
            if(len <= s && rep[s - len]) {
                rep[s] = true;
                par[s] = len;
                break;
            }
        }
    }

    int g = 0;
    for(int len: lengths) {
        if(len <= dim) {
            g = gcd(g, len);
        }
    }

    vector<int> canon(dim + 1);
    if(g == 0) {
        for(int s = 0; s <= dim; s++) {
            canon[s] = s;
        }
    } else {
        int pre = 0;
        for(int s = 0; s <= dim; s++) {
            if((bool)rep[s] != (s % g == 0)) {
                pre = s + 1;
            }
        }
        for(int s = 0; s <= dim; s++) {
            canon[s] = s < pre ? s : pre + (s - pre) % g;
        }
    }

    bool transposed = n > m;
    int h = min(n, m), w = max(n, m);

    vector<vector<int>> horiz(h, vector<int>(w, 0));
    bool possible = true;

    if(rep[w]) {
        for(auto& row: horiz) {
            fill(row.begin(), row.end(), 1);
        }
    } else if(!rep[h]) {
        vector<int> valid_cols;
        for(int mask = 0; mask < (1 << h); mask++) {
            bool ok = true;
            int r = 0;
            while(r < h) {
                if(((mask >> r) & 1) == 0) {
                    int r2 = r;
                    while(r2 < h && ((mask >> r2) & 1) == 0) {
                        r2++;
                    }
                    if(!rep[r2 - r]) {
                        ok = false;
                        break;
                    }
                    r = r2;
                } else {
                    r++;
                }
            }
            if(ok) {
                valid_cols.push_back(mask);
            }
        }

        struct node {
            vector<int> runs;
            int parent;
            int mask;
        };

        vector<vector<node>> layers(w + 1);
        vector<map<vector<int>, int>> seen(w + 1);
        layers[0].push_back({vector<int>(h, 0), -1, -1});
        seen[0][vector<int>(h, 0)] = 0;

        auto key_of = [&](const vector<int>& runs) {
            vector<int> key(h);
            for(int r = 0; r < h; r++) {
                key[r] = canon[runs[r]];
            }
            return key;
        };

        for(int c = 0; c < w; c++) {
            for(int i = 0; i < (int)layers[c].size(); i++) {
                const vector<int>& runs = layers[c][i].runs;
                for(int mask: valid_cols) {
                    vector<int> nxt(h);
                    bool ok = true;
                    for(int r = 0; r < h; r++) {
                        if((mask >> r) & 1) {
                            nxt[r] = runs[r] + 1;
                        } else {
                            if(runs[r] > 0 && !rep[runs[r]]) {
                                ok = false;
                                break;
                            }
                            nxt[r] = 0;
                        }
                    }

                    if(!ok) {
                        continue;
                    }

                    vector<int> key = key_of(nxt);
                    if(seen[c + 1].find(key) == seen[c + 1].end()) {
                        seen[c + 1][key] = layers[c + 1].size();
                        layers[c + 1].push_back({nxt, i, mask});
                    }
                }
            }
        }

        int final_idx = -1;
        for(int i = 0; i < (int)layers[w].size(); i++) {
            bool ok = true;
            for(int r = 0; r < h; r++) {
                if(layers[w][i].runs[r] > 0 && !rep[layers[w][i].runs[r]]) {
                    ok = false;
                    break;
                }
            }
            if(ok) {
                final_idx = i;
                break;
            }
        }

        if(final_idx == -1) {
            possible = false;
        } else {
            int idx = final_idx;
            for(int c = w; c >= 1; c--) {
                int mask = layers[c][idx].mask;
                for(int r = 0; r < h; r++) {
                    horiz[r][c - 1] = (mask >> r) & 1;
                }
                idx = layers[c][idx].parent;
            }
        }
    }

    if(!possible) {
        cout << "NO\n";
        return;
    }

    vector<vector<int>> bid(h, vector<int>(w, -1));
    int next_id = 0;
    for(int r = 0; r < h; r++) {
        int c = 0;
        while(c < w) {
            if(horiz[r][c] == 1) {
                int c2 = c;
                while(c2 < w && horiz[r][c2] == 1) {
                    c2++;
                }

                int pos = c, rem = c2 - c;
                while(rem > 0) {
                    int len = par[rem];
                    for(int t = 0; t < len; t++) {
                        bid[r][pos + t] = next_id;
                    }
                    next_id++;
                    pos += len;
                    rem -= len;
                }

                c = c2;
            } else {
                c++;
            }
        }
    }

    for(int c = 0; c < w; c++) {
        int r = 0;
        while(r < h) {
            if(horiz[r][c] == 0) {
                int r2 = r;
                while(r2 < h && horiz[r2][c] == 0) {
                    r2++;
                }

                int pos = r, rem = r2 - r;
                while(rem > 0) {
                    int len = par[rem];
                    for(int t = 0; t < len; t++) {
                        bid[pos + t][c] = next_id;
                    }
                    next_id++;
                    pos += len;
                    rem -= len;
                }

                r = r2;
            } else {
                r++;
            }
        }
    }

    int b = next_id;
    vector<set<int>> nbr(b);
    for(int r = 0; r < h; r++) {
        for(int c = 0; c < w; c++) {
            if(c + 1 < w && bid[r][c] != bid[r][c + 1]) {
                nbr[bid[r][c]].insert(bid[r][c + 1]);
                nbr[bid[r][c + 1]].insert(bid[r][c]);
            }
            if(r + 1 < h && bid[r][c] != bid[r + 1][c]) {
                nbr[bid[r][c]].insert(bid[r + 1][c]);
                nbr[bid[r + 1][c]].insert(bid[r][c]);
            }
        }
    }

    vector<int> deg(b), order;
    vector<char> removed(b, false);
    for(int i = 0; i < b; i++) {
        deg[i] = nbr[i].size();
    }

    for(int step = 0; step < b; step++) {
        int u = -1;
        for(int i = 0; i < b; i++) {
            if(!removed[i] && (u == -1 || deg[i] < deg[u])) {
                u = i;
            }
        }

        removed[u] = true;
        order.push_back(u);
        for(int v: nbr[u]) {
            if(!removed[v]) {
                deg[v]--;
            }
        }
    }

    vector<int> color(b, -1);
    for(int i = b - 1; i >= 0; i--) {
        int u = order[i];
        set<int> used;
        for(int v: nbr[u]) {
            if(color[v] != -1) {
                used.insert(color[v]);
            }
        }

        int col = 0;
        while(used.count(col)) {
            col++;
        }
        color[u] = col;
    }

    vector<string> out(n, string(m, '?'));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            int id = transposed ? bid[j][i] : bid[i][j];
            out[i][j] = 'a' + color[id];
        }
    }

    cout << "YES\n";
    for(auto& row: out) {
        cout << row << '\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
from math import gcd


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

    n, m, k = data[0], data[1], data[2]
    lengths = data[3:3 + k]

    dim = max(n, m)

    # rep[x] = True if x can be represented as a sum of allowed lengths.
    rep = [False] * (dim + 1)

    # par[x] stores one brick length used in a representation of x.
    par = [-1] * (dim + 1)

    rep[0] = True

    # Unbounded knapsack / coin change DP.
    for s in range(1, dim + 1):
        for length in lengths:
            if length <= s and rep[s - length]:
                rep[s] = True
                par[s] = length
                break

    # GCD of usable brick lengths.
    g = 0

    for length in lengths:
        if length <= dim:
            g = gcd(g, length)

    # canon[x] is the compressed representative of run length x.
    canon = [0] * (dim + 1)

    if g == 0:
        # No brick length fits at all.
        for x in range(dim + 1):
            canon[x] = x
    else:
        pre = 0

        # Find suffix where representability equals divisibility by gcd.
        for x in range(dim + 1):
            if rep[x] != (x % g == 0):
                pre = x + 1

        for x in range(dim + 1):
            if x < pre:
                canon[x] = x
            else:
                canon[x] = pre + (x - pre) % g

    # Work internally with smaller side as height.
    transposed = n > m

    h = min(n, m)
    w = max(n, m)

    # horiz[r][c] = 1 means horizontal orientation.
    # horiz[r][c] = 0 means vertical orientation.
    horiz = [[0] * w for _ in range(h)]

    possible = True

    if rep[w]:
        # Whole rows can be tiled horizontally.
        for r in range(h):
            for c in range(w):
                horiz[r][c] = 1

    elif not rep[h]:
        # Hard case: need mixed orientations.

        valid_cols = []

        # Precompute valid column masks.
        for mask in range(1 << h):
            ok = True
            r = 0

            while r < h:
                if ((mask >> r) & 1) == 0:
                    r2 = r

                    while r2 < h and ((mask >> r2) & 1) == 0:
                        r2 += 1

                    run_len = r2 - r

                    if not rep[run_len]:
                        ok = False
                        break

                    r = r2
                else:
                    r += 1

            if ok:
                valid_cols.append(mask)

        # layers[c] stores states after processing c columns.
        # State is a tuple: (runs, parent_index, mask_used)
        layers = [[] for _ in range(w + 1)]

        # seen[c] maps compressed state keys to their index in layers[c].
        seen = [dict() for _ in range(w + 1)]

        start = tuple([0] * h)
        layers[0].append((start, -1, -1))
        seen[0][start] = 0

        def key_of(runs):
            return tuple(canon[x] for x in runs)

        # DP over columns.
        for c in range(w):
            for i, (runs, parent, old_mask) in enumerate(layers[c]):
                for mask in valid_cols:
                    nxt = [0] * h
                    ok = True

                    for r in range(h):
                        if (mask >> r) & 1:
                            # Horizontal cell extends current run.
                            nxt[r] = runs[r] + 1
                        else:
                            # Vertical cell closes current horizontal run.
                            if runs[r] > 0 and not rep[runs[r]]:
                                ok = False
                                break

                            nxt[r] = 0

                    if not ok:
                        continue

                    nxt_tuple = tuple(nxt)
                    key = key_of(nxt_tuple)

                    if key not in seen[c + 1]:
                        seen[c + 1][key] = len(layers[c + 1])
                        layers[c + 1].append((nxt_tuple, i, mask))

        # Find accepting final state.
        final_idx = -1

        for i, (runs, parent, mask) in enumerate(layers[w]):
            ok = True

            for r in range(h):
                if runs[r] > 0 and not rep[runs[r]]:
                    ok = False
                    break

            if ok:
                final_idx = i
                break

        if final_idx == -1:
            possible = False
        else:
            # Reconstruct orientation matrix.
            idx = final_idx

            for c in range(w, 0, -1):
                runs, parent, mask = layers[c][idx]

                for r in range(h):
                    horiz[r][c - 1] = (mask >> r) & 1

                idx = parent

    # Else:
    # rep[w] is False and rep[h] is True.
    # The default all-zero orientation means all columns are vertical.

    if not possible:
        print("NO")
        return

    # bid[r][c] = brick ID covering internal cell (r, c).
    bid = [[-1] * w for _ in range(h)]

    next_id = 0

    # Split horizontal runs of 1s into bricks.
    for r in range(h):
        c = 0

        while c < w:
            if horiz[r][c] == 1:
                c2 = c

                while c2 < w and horiz[r][c2] == 1:
                    c2 += 1

                pos = c
                rem = c2 - c

                while rem > 0:
                    length = par[rem]

                    for t in range(length):
                        bid[r][pos + t] = next_id

                    next_id += 1
                    pos += length
                    rem -= length

                c = c2
            else:
                c += 1

    # Split vertical runs of 0s into bricks.
    for c in range(w):
        r = 0

        while r < h:
            if horiz[r][c] == 0:
                r2 = r

                while r2 < h and horiz[r2][c] == 0:
                    r2 += 1

                pos = r
                rem = r2 - r

                while rem > 0:
                    length = par[rem]

                    for t in range(length):
                        bid[pos + t][c] = next_id

                    next_id += 1
                    pos += length
                    rem -= length

                r = r2
            else:
                r += 1

    brick_count = next_id

    # Build adjacency graph of bricks.
    graph = [set() for _ in range(brick_count)]

    for r in range(h):
        for c in range(w):
            if c + 1 < w and bid[r][c] != bid[r][c + 1]:
                a = bid[r][c]
                b = bid[r][c + 1]

                graph[a].add(b)
                graph[b].add(a)

            if r + 1 < h and bid[r][c] != bid[r + 1][c]:
                a = bid[r][c]
                b = bid[r + 1][c]

                graph[a].add(b)
                graph[b].add(a)

    # Smallest-last ordering.
    deg = [len(graph[i]) for i in range(brick_count)]
    removed = [False] * brick_count
    order = []

    for _ in range(brick_count):
        u = -1

        for i in range(brick_count):
            if not removed[i] and (u == -1 or deg[i] < deg[u]):
                u = i

        removed[u] = True
        order.append(u)

        for v in graph[u]:
            if not removed[v]:
                deg[v] -= 1

    # Greedy coloring in reverse smallest-last order.
    color = [-1] * brick_count

    for u in reversed(order):
        used = set()

        for v in graph[u]:
            if color[v] != -1:
                used.add(color[v])

        col = 0

        while col in used:
            col += 1

        color[u] = col

    # Convert internal board back to original orientation.
    answer = [['?'] * m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            if transposed:
                brick_id = bid[j][i]
            else:
                brick_id = bid[i][j]

            answer[i][j] = chr(ord('a') + color[brick_id])

    print("YES")

    for row in answer:
        print(''.join(row))


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