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

250. Constructive Plan
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



"Oh, no!" --- Petya said, walking around his recently bought ground plot. Petya wants to build a new house on it. According to Petya's building project the house should look from above like "C" character.
There are many trees growing on Petya's plot. But everyone who cuts down a tree in Petya's country is sent to cut down trees for the rest of his life. So first of all Petya has to choose a place for building the house without cutting any tree.
He is feeling that he is not able to find the solution on his own, so he decided to ask you to help him.
The task is simplified a little by the fact that Petya's plot has a rectangular shape of size N*M, divided into 1*1 square cells. For each cell it is known whether there are any trees growing there. House can't occupy cells where trees grow.
Fortunately Petya could explain how his house must look from above.
1) House must consist of three rectangular blocks.
2) Area of each block must be greater than zero.
3) These blocks must touch each other, but can't overlap.
4) Left-top cells of all blocks must be on one vertical.
5) The width of the middle block must be less than the width of upper and lower blocks.
Petya wants to build a house with maximal possible area.

Input
The first line of input contains integers N and M (1<=N,M<=180) separated by whitespace. Each of the following N lines contains M integer numbers separated by whitespaces. Each number is either 0 or 1; 1 means that there are trees in the cell, 0 means that the cell is empty.

Output
On the first line output maximal possible area. After that output N lines that describe your plan in the same format as in the input. If the cell is occupied by the house, write 8 instead of 0. If it is impossible to solve problem, output "-1" (without quotes).

Sample test(s)

Input
Test #1
8 7
1 1 1 1 1 1 1
1 1 0 0 0 0 1
1 1 0 0 0 0 1
1 1 0 0 0 0 1
1 1 0 0 0 0 1
1 1 0 0 0 0 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1

Test #2
8 8
1 1 1 1 1 1 1 1
1 0 0 0 0 1 0 1
1 1 1 1 0 0 0 1
1 0 0 0 0 0 0 1
1 1 0 0 0 0 0 1
1 0 1 0 1 0 0 1
1 0 0 0 0 0 1 1
1 1 1 1 1 1 1 1

Output
Test #1
19
1 1 1 1 1 1 1
1 1 8 8 8 8 1
1 1 8 8 8 8 1
1 1 8 8 8 0 1
1 1 8 8 8 8 1
1 1 8 8 8 8 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
Test #2
12
1 1 1 1 1 1 1 1
1 0 0 0 0 1 0 1
1 1 1 1 0 0 0 1
1 0 0 8 8 8 8 1
1 1 0 8 8 8 8 1
1 0 1 8 1 0 0 1
1 0 0 8 8 8 1 1
1 1 1 1 1 1 1 1
Author:	Antony Popovich
Resource:	Petrozavodsk Summer Training Sessions 2004
Date:	August 25, 2004

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

Given an `N × M` grid (`1 ≤ N, M ≤ 180`) with cells `0` (empty) and `1` (tree), place a house shaped like the letter **C** consisting of **three non-overlapping rectangles**: **top**, **middle**, **bottom**.

Constraints for the 3 rectangles:
- Each has **positive area**.
- They **touch** (share a side boundary with neighbors) but **do not overlap**.
- The **top-left cell** of all three rectangles lies in the **same column** (same left edge).
- Middle rectangle width is **strictly smaller** than both top and bottom widths.
- House cells must be on `0` cells only.

Maximize total area.  
Output the maximum area and a plan where house cells are marked `8` (trees stay `1`, other empty stay `0`). If impossible, output `-1`.

---

## 2) Key observations

1. **Fix the common left edge column `c`.**  
   All three rectangles must start at the same column, so we can try each `c = 0..M-1`.

2. For a fixed `c`, each row `r` has a maximum possible width:
   \[
   height[r] = \text{# consecutive zeros starting from }(r,c)\text{ to the right}
   \]
   Any rectangle starting at column `c` and spanning rows `[a..b]` can have width at most:
   \[
   \min(height[a..b])
   \]

3. The classic “largest rectangle in histogram” toolkit applies:
   - Compute nearest row above with smaller `height` (`l[i]`)
   - Compute nearest row below with smaller `height` (`r[i]`)
   Using monotonic stacks in `O(N)`.

4. We need **three stacked rectangles** with widths `w1` (top), `w2` (middle), `w3` (bottom), and:
   - `w2 < w1` and `w2 < w3`, all widths > 0
   - Top touches middle, middle touches bottom (adjacent vertically)

5. When choosing “critical rows” `i` (defines `w1 = height[i]`) and `j` (defines `w3 = height[j]`, with `j ≥ i+2` so there’s at least one row for middle), the middle part falls into 3 structural cases based on histogram spans. Each case gives an `O(1)` formula for best `w2` and the row ranges—if we can query `min(height[L..R])` quickly.

6. Since `N ≤ 180`, we can precompute:
   \[
   min\_h[a][b] = \min(height[a..b])
   \]
   in `O(N^2)` per column, and then evaluate each `(i,j)` in `O(1)`.

Overall complexity: `O(M * N^2)` which is feasible for 180.

---

## 3) Full solution approach

### Step A — Precompute rightward empty lengths (`dist`)
For each cell `(r,c)`:
- If it’s a tree (`1`), `dist[r][c] = 0`
- Else `dist[r][c] = 1 + dist[r][c+1]` (scan each row right-to-left)

This allows `height[r] = dist[r][fixed_col]`.

### Step B — Solve best “C” for one fixed left column `c`
Build histogram array:
- `height[r] = dist[r][c]`

Compute nearest strictly smaller:
- `l[i]`: nearest index `< i` with `height[l[i]] < height[i]` (or `-1`)
- `r[i]`: nearest index `> i` with `height[r[i]] < height[i]` (or `n`)

Precompute range minima:
- `min_h[a][b] = min(height[a..b])` for all `a ≤ b`

Now enumerate pairs:
- Choose `i` for the top (must have `height[i] > 0`)
- Choose `j` for the bottom (`j ≥ i+2`, `height[j] > 0`)

Let:
- `w1 = height[i]`, `w3 = height[j]`
- Top can start at `top_start = l[i] + 1`
- Bottom can end at `bot_end = r[j] - 1`

We consider three cases:

#### Case 1: `r[i] >= j`
The “support” region of width `w1` reaches down to `j` (no guaranteed gap).  
We can place the middle as a **single row** and set:
- `w2 = min(w1, w3) - 1` (strictly smaller than both)
- Choose a middle row `mid_row` near the boundary so rectangles touch:
  - `mid_row = max(i + 1, l[j])`
- Then:
  - Top rows: `[top_start .. mid_row-1]` width `w1`
  - Middle row: `[mid_row .. mid_row]` width `w2`
  - Bottom rows: `[mid_row+1 .. bot_end]` width `w3`

Check `w2 > 0`.

#### Case 2: `l[j] <= i`
Symmetric version: also possible to place 1-row middle near the other boundary:
- `mid_row = min(j - 1, r[i])`
- same `w2 = min(w1, w3) - 1`

#### Case 3: `r[i] <= l[j]`
There is a real middle band of rows `[r[i] .. l[j]]`. Middle can have height > 1:
- `mid_start = r[i]`, `mid_end = l[j]`
- Middle width must satisfy:
  - `w2 ≤ w1 - 1`
  - `w2 ≤ w3 - 1`
  - `w2 ≤ min(height[mid_start..mid_end])`
So:
\[
w2 = \min(w1-1, w3-1, min\_h[mid\_start][mid\_end])
\]
Check `w2 > 0`.
Top becomes `[top_start..r[i]-1]`, bottom becomes `[l[j]+1..bot_end]`.

Compute area for each valid construction and keep the best configuration for this column.

### Step C — Try all columns and reconstruct
Take the best among all columns. If none, output `-1`.  
Otherwise, paint the three rectangles with `8` and print the grid.

---

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

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

int n, m;
vector<vector<int>> grid;
vector<vector<int>> distRight; // distRight[r][c] = consecutive empty cells (0) to the right starting at (r,c)

struct Result {
    int area = -1;
    int col = -1;              // common left edge column

    // top rectangle: rows [r1s..r1e], width w1
    int r1s=-1, r1e=-1, w1=-1;
    // middle rectangle: rows [r2s..r2e], width w2
    int r2s=-1, r2e=-1, w2=-1;
    // bottom rectangle: rows [r3s..r3e], width w3
    int r3s=-1, r3e=-1, w3=-1;
};

static inline void ckmax(Result &best, const Result &cand) {
    if (cand.area > best.area) best = cand;
}

// Solve best C-shape with fixed left edge at column 'col'
Result solveHistogram(int col) {
    vector<int> height(n);
    for (int r = 0; r < n; r++) height[r] = distRight[r][col];

    // l[i] = nearest index above i with strictly smaller height, else -1
    // r[i] = nearest index below i with strictly smaller height, else n
    vector<int> l(n), r(n);
    {
        vector<int> st;
        st.reserve(n);
        for (int i = 0; i < n; i++) {
            while (!st.empty() && height[st.back()] >= height[i]) st.pop_back();
            l[i] = st.empty() ? -1 : st.back();
            st.push_back(i);
        }
    }
    {
        vector<int> st;
        st.reserve(n);
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && height[st.back()] >= height[i]) st.pop_back();
            r[i] = st.empty() ? n : st.back();
            st.push_back(i);
        }
    }

    // min_h[a][b] = min(height[a..b]) for a<=b, computed in O(n^2)
    vector<vector<int>> min_h(n, vector<int>(n, INT_MAX));
    for (int i = 0; i < n; i++) {
        int cur = height[i];
        min_h[i][i] = cur;
        for (int j = i + 1; j < n; j++) {
            cur = min(cur, height[j]);
            min_h[i][j] = cur;
        }
    }

    Result best;

    for (int i = 0; i < n; i++) {
        if (height[i] == 0) continue;  // cannot place positive-width top

        int w1 = height[i];
        int top_start = l[i] + 1;

        for (int j = i + 2; j < n; j++) {
            if (height[j] == 0) continue; // cannot place positive-width bottom

            int w3 = height[j];
            int bot_end = r[j] - 1;

            // Case 1: r[i] >= j => can place 1-row middle
            if (r[i] >= j) {
                int mid_row = max(i + 1, l[j]);
                int top_end = mid_row - 1;
                int bot_start = mid_row + 1;

                int w2 = min(w1, w3) - 1; // strictly smaller than both
                if (w2 > 0) {
                    int area = (top_end - top_start + 1) * w1
                             + w2
                             + (bot_end - bot_start + 1) * w3;

                    Result cand;
                    cand.area = area; cand.col = col;
                    cand.r1s = top_start; cand.r1e = top_end; cand.w1 = w1;
                    cand.r2s = mid_row;   cand.r2e = mid_row; cand.w2 = w2;
                    cand.r3s = bot_start; cand.r3e = bot_end; cand.w3 = w3;
                    ckmax(best, cand);
                }
            }

            // Case 2: l[j] <= i => symmetric 1-row middle
            if (l[j] <= i) {
                int mid_row = min(j - 1, r[i]);
                int top_end = mid_row - 1;
                int bot_start = mid_row + 1;

                int w2 = min(w1, w3) - 1;
                if (w2 > 0) {
                    int area = (top_end - top_start + 1) * w1
                             + w2
                             + (bot_end - bot_start + 1) * w3;

                    Result cand;
                    cand.area = area; cand.col = col;
                    cand.r1s = top_start; cand.r1e = top_end; cand.w1 = w1;
                    cand.r2s = mid_row;   cand.r2e = mid_row; cand.w2 = w2;
                    cand.r3s = bot_start; cand.r3e = bot_end; cand.w3 = w3;
                    ckmax(best, cand);
                }
            }

            // Case 3: r[i] <= l[j] => a true middle band exists
            if (r[i] <= l[j]) {
                int top_end = r[i] - 1;
                int bot_start = l[j] + 1;

                int mid_start = r[i];
                int mid_end = l[j];

                int min_middle = min_h[mid_start][mid_end];
                int w2 = min({w1 - 1, w3 - 1, min_middle});
                if (w2 > 0) {
                    int area = (top_end - top_start + 1) * w1
                             + (mid_end - mid_start + 1) * w2
                             + (bot_end - bot_start + 1) * w3;

                    Result cand;
                    cand.area = area; cand.col = col;
                    cand.r1s = top_start; cand.r1e = top_end; cand.w1 = w1;
                    cand.r2s = mid_start; cand.r2e = mid_end; cand.w2 = w2;
                    cand.r3s = bot_start; cand.r3e = bot_end; cand.w3 = w3;
                    ckmax(best, cand);
                }
            }
        }
    }

    return best;
}

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

    cin >> n >> m;
    grid.assign(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    // Precompute distRight: consecutive zeros to the right (including itself)
    distRight.assign(n, vector<int>(m, 0));
    for (int r = 0; r < n; r++) {
        for (int c = m - 1; c >= 0; c--) {
            if (grid[r][c] == 1) distRight[r][c] = 0;
            else distRight[r][c] = 1 + (c + 1 < m ? distRight[r][c + 1] : 0);
        }
    }

    // Try each column as common left edge
    Result best;
    for (int col = 0; col < m; col++) {
        Result cand = solveHistogram(col);
        ckmax(best, cand);
    }

    if (best.area < 0) {
        cout << -1 << "\n";
        return 0;
    }

    // Paint the rectangles with 8
    auto paint = [&](int rs, int re, int w) {
        for (int r = rs; r <= re; r++) {
            for (int c = best.col; c < best.col + w; c++) {
                grid[r][c] = 8;
            }
        }
    };

    paint(best.r1s, best.r1e, best.w1);
    paint(best.r2s, best.r2e, best.w2);
    paint(best.r3s, best.r3e, best.w3);

    // Output
    cout << best.area << "\n";
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (c) cout << ' ';
            cout << grid[r][c];
        }
        cout << "\n";
    }
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))

    grid = [[int(next(it)) for _ in range(m)] for _ in range(n)]

    # dist_right[r][c] = consecutive empty cells to the right from (r,c), including (r,c)
    dist_right = [[0] * m for _ in range(n)]
    for r in range(n):
        for c in range(m - 1, -1, -1):
            if grid[r][c] == 1:
                dist_right[r][c] = 0
            else:
                dist_right[r][c] = 1 + (dist_right[r][c + 1] if c + 1 < m else 0)

    best_area = -1
    best = None  # (col, r1s,r1e,w1, r2s,r2e,w2, r3s,r3e,w3)

    for col in range(m):
        height = [dist_right[r][col] for r in range(n)]

        # nearest strictly smaller above: l[i]
        l = [-1] * n
        st = []
        for i in range(n):
            while st and height[st[-1]] >= height[i]:
                st.pop()
            l[i] = st[-1] if st else -1
            st.append(i)

        # nearest strictly smaller below: r[i]
        rgt = [n] * n
        st.clear()
        for i in range(n - 1, -1, -1):
            while st and height[st[-1]] >= height[i]:
                st.pop()
            rgt[i] = st[-1] if st else n
            st.append(i)

        # min_h[a][b] = min(height[a..b]) for O(1) range minima in case 3
        min_h = [[10**9] * n for _ in range(n)]
        for i in range(n):
            cur = height[i]
            min_h[i][i] = cur
            for j in range(i + 1, n):
                if height[j] < cur:
                    cur = height[j]
                min_h[i][j] = cur

        # enumerate critical rows i (top) and j (bottom)
        for i in range(n):
            if height[i] == 0:
                continue
            w1 = height[i]
            top_start = l[i] + 1

            for j in range(i + 2, n):
                if height[j] == 0:
                    continue
                w3 = height[j]
                bot_end = rgt[j] - 1

                # Case 1: r[i] >= j => 1-row middle
                if rgt[i] >= j:
                    mid = max(i + 1, l[j])
                    top_end = mid - 1
                    bot_start = mid + 1
                    w2 = min(w1, w3) - 1
                    if w2 > 0:
                        area = (top_end - top_start + 1) * w1 + w2 + (bot_end - bot_start + 1) * w3
                        if area > best_area:
                            best_area = area
                            best = (col,
                                    top_start, top_end, w1,
                                    mid, mid, w2,
                                    bot_start, bot_end, w3)

                # Case 2: l[j] <= i => symmetric 1-row middle
                if l[j] <= i:
                    mid = min(j - 1, rgt[i])
                    top_end = mid - 1
                    bot_start = mid + 1
                    w2 = min(w1, w3) - 1
                    if w2 > 0:
                        area = (top_end - top_start + 1) * w1 + w2 + (bot_end - bot_start + 1) * w3
                        if area > best_area:
                            best_area = area
                            best = (col,
                                    top_start, top_end, w1,
                                    mid, mid, w2,
                                    bot_start, bot_end, w3)

                # Case 3: r[i] <= l[j] => true middle band
                if rgt[i] <= l[j]:
                    top_end = rgt[i] - 1
                    bot_start = l[j] + 1
                    mid_start = rgt[i]
                    mid_end = l[j]

                    w2 = min(w1 - 1, w3 - 1, min_h[mid_start][mid_end])
                    if w2 > 0:
                        area = ((top_end - top_start + 1) * w1
                                + (mid_end - mid_start + 1) * w2
                                + (bot_end - bot_start + 1) * w3)
                        if area > best_area:
                            best_area = area
                            best = (col,
                                    top_start, top_end, w1,
                                    mid_start, mid_end, w2,
                                    bot_start, bot_end, w3)

    if best_area < 0:
        sys.stdout.write("-1\n")
        return

    col, r1s, r1e, w1, r2s, r2e, w2, r3s, r3e, w3 = best

    def paint(rs, re, w):
        for rr in range(rs, re + 1):
            for cc in range(col, col + w):
                grid[rr][cc] = 8

    paint(r1s, r1e, w1)
    paint(r2s, r2e, w2)
    paint(r3s, r3e, w3)

    out = [str(best_area)]
    out.extend(" ".join(map(str, row)) for row in grid)
    sys.stdout.write("\n".join(out) + "\n")


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

These implementations follow the editorial strategy: fix the left edge, convert to a histogram of allowed widths, use nearest-smaller boundaries plus a precomputed range-min table to evaluate all valid C-shapes efficiently, then reconstruct the best one.