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

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;
vector<vector<int>> grid;
vector<vector<int>> dist;

struct Result {
    int area;
    int col;
    int r1_start, r1_end, w1;
    int r2_start, r2_end, w2;
    int r3_start, r3_end, w3;

    Result()
        : area(-1),
          col(-1),
          r1_start(-1),
          r1_end(-1),
          w1(-1),
          r2_start(-1),
          r2_end(-1),
          w2(-1),
          r3_start(-1),
          r3_end(-1),
          w3(-1) {}

    Result(
        int a, int c, int rs1, int re1, int ww1, int rs2, int re2, int ww2,
        int rs3, int re3, int ww3
    )
        : area(a),
          col(c),
          r1_start(rs1),
          r1_end(re1),
          w1(ww1),
          r2_start(rs2),
          r2_end(re2),
          w2(ww2),
          r3_start(rs3),
          r3_end(re3),
          w3(ww3) {}
};

void read() {
    cin >> n >> m;
    grid.assign(n, vector<int>(m));
    cin >> grid;
    dist.assign(n, vector<int>(m));
    for(int row = 0; row < n; row++) {
        for(int col = m - 1; col >= 0; col--) {
            if(grid[row][col] == 1) {
                dist[row][col] = 0;
            } else {
                dist[row][col] = (col == m - 1) ? 1 : dist[row][col + 1] + 1;
            }
        }
    }
}

Result solve_histogram(int col) {
    vector<int> height(n);
    for(int row = 0; row < n; row++) {
        height[row] = dist[row][col];
    }

    vector<int> l(n), r(n);
    stack<int> s;

    for(int i = 0; i < n; i++) {
        while(!s.empty() && height[s.top()] >= height[i]) {
            s.pop();
        }
        l[i] = s.empty() ? -1 : s.top();
        s.push(i);
    }
    while(!s.empty()) {
        s.pop();
    }

    for(int i = n - 1; i >= 0; i--) {
        while(!s.empty() && height[s.top()] >= height[i]) {
            s.pop();
        }
        r[i] = s.empty() ? n : s.top();
        s.push(i);
    }

    vector<vector<int>> min_h(n, vector<int>(n, INT_MAX));
    for(int i = 0; i < n; i++) {
        min_h[i][i] = height[i];
        for(int j = i + 1; j < n; j++) {
            min_h[i][j] = min(min_h[i][j - 1], height[j]);
        }
    }

    Result best;
    for(int i = 0; i < n; i++) {
        if(height[i] == 0) {
            continue;
        }

        int top_start = l[i] + 1, top_end;
        for(int j = i + 2; j < n; j++) {
            if(height[j] == 0) {
                continue;
            }

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

            if(r[i] >= j) {
                int mid_row = max(i + 1, l[j]);
                top_end = mid_row - 1;
                bot_start = mid_row + 1;

                int w2 = min(w1, w3) - 1;
                int area = (top_end - top_start + 1) * w1 + 1 * w2 +
                           (bot_end - bot_start + 1) * w3;
                if(w2 > 0 && area > best.area) {
                    best = Result(
                        area, col, top_start, top_end, w1, mid_row, mid_row, w2,
                        bot_start, bot_end, w3
                    );
                }
            }

            if(l[j] <= i) {
                int mid_row = min(j - 1, r[i]);
                top_end = mid_row - 1;
                bot_start = mid_row + 1;

                int w2 = min(w1, w3) - 1;
                int area = (top_end - top_start + 1) * w1 + 1 * w2 +
                           (bot_end - bot_start + 1) * w3;
                if(w2 > 0 && area > best.area) {
                    best = Result(
                        area, col, top_start, top_end, w1, mid_row, mid_row, w2,
                        bot_start, bot_end, w3
                    );
                }
            }

            if(r[i] <= l[j]) {
                top_end = r[i] - 1;
                bot_start = l[j] + 1;

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

                int min_middle = min_h[r[i]][l[j]];
                int w2 = min({w1 - 1, w3 - 1, min_middle});
                int area = (top_end - top_start + 1) * w1 +
                           (mid_end - mid_start + 1) * w2 +
                           (bot_end - bot_start + 1) * w3;
                if(w2 > 0 && area > best.area) {
                    best = Result(
                        area, col, top_start, top_end, w1, mid_start, mid_end,
                        w2, bot_start, bot_end, w3
                    );
                }
            }
        }
    }

    return best;
}

void solve() {
    // Implementing this problem is non-trivial, but the core idea is to think
    // about how the largest sub-rectangle problem is solved, and adapt the
    // solution. More precisely, there is a popular approach with building a
    // "histogram" of the heights of empty places, and then using stacks find
    // the closest columns that are smaller as they define how far we can extend
    // the current column. There is a Geeks-for-Geeks page describing the idea
    // further:
    //
    //     www.geeksforgeeks.org/dsa/maximum-size-rectangle-binary-sub-matrix-1s
    //
    // In this problem we have to choose 3 adjacent rectangles. We know that
    // their leftmost points should fall on the same vertical line. Let's try to
    // independently solve (find best possible answer) for every column in O(M).
    // We can build a histogram with the distances to the right from each cell
    // in this column. Let's try to fix i + 1 < j - the "critical" column in the
    // top and bottom rectangles out of the three. We can easily precompute with
    // a stack l[i] and r[i] as the closest positions smaller than height[i],
    // and we should trivially extend the top and bottom rectangles to l[i] and
    // r[j]. The area between i and j is a bit trickier as we have a few cases:
    //
    //     1) r[i] >= j. In that case the height of the middle column should be
    //        simply min(height[i], height[j])-1, and we can have a rectangle of
    //        length 1 directly adjacent to the larger of i and j. To be more
    //        precise, we should first try to extend j as far as possible to the
    //        left, then put the middle with width 1, and finally have the rest
    //        for i.
    //
    //     2) l[j] <= i. This is symmetric to the (1) case.
    //
    //     3) If it's neither (1) or (2), we have r[i] <= l[j]. In this case, we
    //        are bounded by min(height[k] for r[i] <= k <= l[j]) for the middle
    //        part. We can do a quadratic precompute of min[L][R] with a simple
    //        DP or a sparse table, so that this case can also be handled in
    //        constant time.
    //
    // As we already mentioned, we are looking at the O(M) histogram, finding
    // the best "C" for a histogram can be done in O(N^2) time. As we have to
    // recover the answer, it's convenient to return the relevant intervals for
    // the 3 portions, as well as the heights and the overall area. Some
    // additional parts to be careful about are heights of 0 as this won't be a
    // valid rectangle.

    Result best;
    for(int col = 0; col < m; col++) {
        Result res = solve_histogram(col);
        if(res.area > best.area) {
            best = res;
        }
    }

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

    cout << best.area << '\n';

    int col = best.col;
    for(int row = best.r1_start; row <= best.r1_end; row++) {
        for(int c = col; c < col + best.w1; c++) {
            grid[row][c] = 8;
        }
    }
    for(int row = best.r2_start; row <= best.r2_end; row++) {
        for(int c = col; c < col + best.w2; c++) {
            grid[row][c] = 8;
        }
    }
    for(int row = best.r3_start; row <= best.r3_end; row++) {
        for(int c = col; c < col + best.w3; c++) {
            grid[row][c] = 8;
        }
    }

    for(int row = 0; row < n; row++) {
        for(int c = 0; c < m; c++) {
            if(c > 0) {
                cout << ' ';
            }
            cout << grid[row][c];
        }
        cout << '\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    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.