## 1. Abridged problem statement

Given an `N x M` rectangle and infinitely many bricks of sizes `1 x L1, 1 x L2, ..., 1 x LK`, determine whether the rectangle can be tiled without overlaps or holes. Bricks may be placed horizontally or vertically.

If impossible, print `NO`.

If possible, print `YES` and an `N x M` grid of lowercase letters. Cells belonging to the same brick must have the same letter, and neighboring cells belonging to different bricks must have different letters.

Constraints:

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

---

## 2. Detailed editorial

### Key observation

Instead of directly placing bricks, first decide only the orientation of the brick covering each cell.

Let:

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

Then:

- In every row, every maximal consecutive segment of `1`s must have length representable as a sum of allowed brick lengths.
- In every column, every maximal consecutive segment of `0`s must have length representable as a sum of allowed brick lengths.

For example, if the available brick lengths are `3` and `4`, then a horizontal run of length `7` is valid because `7 = 3 + 4`.

After such a valid orientation matrix is built, every run can be split into actual bricks using a simple dynamic programming parent array.

---

### Step 1: Compute representable lengths

Let `rep[x]` mean that length `x` can be written as a non-negative sum of given brick lengths.

We compute it like the classic unbounded knapsack / coin change 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;
```

We also store `par[s]`, one brick length used to form `s`, so later we can reconstruct the actual bricks.

---

### Step 2: Handle easy cases

Let:

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

The algorithm internally works with the shorter side as height to keep masks small.

There are two easy cases:

#### Case 1: `w` is representable

Then every row can be tiled horizontally.

So the whole internal matrix is filled with `1`.

#### Case 2: `w` is not representable, but `h` is representable

Then every column can be tiled vertically.

So the whole internal matrix is filled with `0`.

---

### Step 3: Hard case — neither side is directly representable

Now we need a mixed orientation matrix.

We process the rectangle column by column.

Each column is represented by a bitmask of length `h`.

For example, if `h = 5`, then a column mask has 5 bits. Bit `r` tells whether row `r` in this column is horizontal or vertical.

A column mask is valid if all maximal vertical runs of `0`s inside it have representable lengths.

Example:

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

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

All valid column masks are precomputed.

---

### Step 4: Dynamic programming over columns

The DP state stores, for every row, the current length of an open horizontal run.

For example:

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

means:

- row `0` currently has no open horizontal run,
- row `1` has an open horizontal run of length `3`,
- row `2` has an open horizontal run of length `1`,
- row `3` currently has no open horizontal run.

When we add a new column mask:

- If bit `r` is `1`, then the horizontal run in row `r` extends by one.
- If bit `r` is `0`, then the horizontal run in row `r` ends. Its length must be representable.

After processing all `w` columns, every still-open horizontal run must also be representable.

If such a DP path exists, we reconstruct the masks and get a valid orientation matrix.

---

### Step 5: State compression

Naively, every row’s open run length could be from `0` to `w`, giving up to `(w + 1)^h` states.

The solution compresses run lengths using eventual periodicity.

Let `g` be the gcd of usable brick lengths. For large enough lengths, representability only depends on length modulo `g`.

So the code maps every run length to a canonical representative before storing it in the visited map.

This greatly reduces the number of states.

---

### Step 6: Convert orientation matrix into actual bricks

Once we have the `0/1` orientation matrix:

- For every horizontal run of `1`s, split it into bricks using `par[]`.
- For every vertical run of `0`s, split it into bricks using `par[]`.

Each brick receives a unique integer ID.

---

### Step 7: Color bricks with letters

Neighboring bricks must have different letters.

Build a graph:

- Each brick is a vertex.
- Two bricks are connected if they share an edge.

This graph is planar. The code uses a smallest-last greedy coloring:

1. Repeatedly remove a vertex of minimum degree.
2. Then color vertices in reverse removal order using the smallest available color.

For planar graphs, this uses at most 6 colors, so lowercase letters are more than enough.

---

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

---

## 4. Python solution

```python
import sys
from math import gcd


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

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

    # Next K integers are allowed brick lengths.
    lengths = data[3:3 + k]

    # We only care about lengths up to the larger rectangle dimension.
    dim = max(n, m)

    # rep[x] tells whether length x can be represented as a sum of brick lengths.
    rep = [False] * (dim + 1)

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

    # Zero length is representable using no bricks.
    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

    # Compute gcd of all usable brick lengths.
    g = 0
    for length in lengths:
        if length <= dim:
            g = gcd(g, length)

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

    if g == 0:
        # No brick can fit at all, so no periodic compression.
        for s in range(dim + 1):
            canon[s] = s
    else:
        # Find where representability stabilizes to "s is divisible by gcd".
        pre = 0
        for s in range(dim + 1):
            if rep[s] != (s % g == 0):
                pre = s + 1

        # Before pre, keep exact lengths.
        # From pre onward, only residue modulo gcd matters.
        for s in range(dim + 1):
            if s < pre:
                canon[s] = s
            else:
                canon[s] = pre + (s - pre) % g

    # Work internally with the smaller dimension as height.
    transposed = n > m
    h = min(n, m)
    w = max(n, m)

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

    possible = True

    if rep[w]:
        # If the width is representable, make every row horizontal.
        for r in range(h):
            for c in range(w):
                horiz[r][c] = 1

    elif not rep[h]:
        # Hard case: neither width nor height is directly representable.

        valid_cols = []

        # Enumerate all column masks of height h.
        for mask in range(1 << h):
            ok = True
            r = 0

            while r < h:
                # Bit 0 means vertical orientation.
                if ((mask >> r) & 1) == 0:
                    r2 = r

                    # Find maximal vertical zero-run.
                    while r2 < h and ((mask >> r2) & 1) == 0:
                        r2 += 1

                    # Its length must be representable.
                    if not rep[r2 - r]:
                        ok = False
                        break

                    r = r2
                else:
                    r += 1

            if ok:
                valid_cols.append(mask)

        # Each DP layer is a list of states.
        # A state is (runs, parent_index, mask_used).
        layers = [[] for _ in range(w + 1)]

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

        # Initial state: no open horizontal runs.
        start_runs = tuple([0] * h)
        layers[0].append((start_runs, -1, -1))
        seen[0][start_runs] = 0

        def key_of(runs):
            # Compress each run length using canon[].
            return tuple(canon[x] for x in runs)

        # Process all columns left to right.
        for c in range(w):
            for i, (runs, parent, old_mask) in enumerate(layers[c]):
                # Try every vertically valid column mask.
                for mask in valid_cols:
                    nxt = [0] * h
                    ok = True

                    for r in range(h):
                        if (mask >> r) & 1:
                            # Horizontal cell extends the run.
                            nxt[r] = runs[r] + 1
                        else:
                            # Vertical cell closes the 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)

                    # Store only one representative of equivalent states.
                    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 column masks.
            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 matrix means all bricks are vertical.

    if not possible:
        print("NO")
        return

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

    next_id = 0

    # Process horizontal runs.
    for r in range(h):
        c = 0

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

                # Find maximal horizontal run of 1s.
                while c2 < w and horiz[r][c2] == 1:
                    c2 += 1

                pos = c
                rem = c2 - c

                # Split run into bricks using par[].
                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

    # Process vertical runs.
    for c in range(w):
        r = 0

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

                # Find maximal vertical run of 0s.
                while r2 < h and horiz[r2][c] == 0:
                    r2 += 1

                pos = r
                rem = r2 - r

                # Split run into bricks using par[].
                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

    # Total number of bricks.
    b = next_id

    # Build adjacency graph between bricks.
    nbr = [set() for _ in range(b)]

    for r in range(h):
        for c in range(w):
            # Right neighbor.
            if c + 1 < w and bid[r][c] != bid[r][c + 1]:
                a = bid[r][c]
                bb = bid[r][c + 1]
                nbr[a].add(bb)
                nbr[bb].add(a)

            # Bottom neighbor.
            if r + 1 < h and bid[r][c] != bid[r + 1][c]:
                a = bid[r][c]
                bb = bid[r + 1][c]
                nbr[a].add(bb)
                nbr[bb].add(a)

    # Smallest-last ordering for greedy coloring.
    deg = [len(nbr[i]) for i in range(b)]
    removed = [False] * b
    order = []

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

        # Pick remaining vertex with minimum degree.
        for i in range(b):
            if not removed[i] and (u == -1 or deg[i] < deg[u]):
                u = i

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

        # Update degrees.
        for v in nbr[u]:
            if not removed[v]:
                deg[v] -= 1

    # Greedy color in reverse removal order.
    color = [-1] * b

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

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

        col = 0
        while col in used:
            col += 1

        color[u] = col

    # Build output grid in original orientation.
    out = [['?'] * 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]

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

    print("YES")
    for row in out:
        print(''.join(row))


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

---

## 5. Compressed editorial

Compute which segment lengths are representable as sums of allowed brick lengths.

Represent a tiling by a `0/1` orientation matrix:

- `1` = horizontal brick cell,
- `0` = vertical brick cell.

Every horizontal run of `1`s must have representable length. Every vertical run of `0`s must have representable length.

Work with the smaller rectangle side as height `h`, so columns can be represented as bitmasks.

If the width is representable, use all-horizontal bricks. If the height is representable, use all-vertical bricks.

Otherwise:

1. Precompute all valid column masks whose zero-runs have representable lengths.
2. Do DP over columns.
3. State stores current open horizontal run length in each row.
4. When a `0` appears, the corresponding run closes and must be representable.
5. After the last column, all still-open runs must also be representable.

Compress run lengths using gcd-based eventual periodicity of representability.

After reconstructing a valid orientation matrix, split each representable run into real bricks using the DP parent array.

Finally, build the brick adjacency graph and greedily color it using smallest-last order. Output colors as lowercase letters.