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

307. Cipher
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



ASN has just invented a brand new cipher. Its key is just a H x W matrix of 0's and 1's. A tool by Macrosoft is recommended to be used as a manager of those keys. This tool stores a fingerprint for each key to protect from storage failures. Such a fingerprint is an (H-1) x (W-1) matrix consisting of 2 x 2 sums; i.e., if A is the key and B is the fingerprint, then Bij=Aij+Ai+1,j+Ai,j+1+Ai+1,j+1. Given the fingerprint, you are to find at least one key with such fingerprint, or to report that the fingerprint is corrupt (in case no key can produce it).

Input
The first line of the input file contains two numbers, H and W (2 ≤ H, W ≤ 300). The next H-1 lines contain W-1 characters each with no spaces in between, describing the fingerprint. Each of those characters will be either 0, 1, 2, 3, or 4.

Output
Output the key using the format similar to that of the input file: output H lines containing W characters (0 or 1) each, with no spaces in between.

If the fingerprint is corrupt, output CORRUPT on the only line of output.

Example(s)
sample input
sample output
3 4
222
222
0110
1001
0110

<|response|>
1. Abridged problem statement  
Given an H×W binary matrix A, you are given its (H−1)×(W−1) “fingerprint” B where  
  B[i][j] = A[i][j] + A[i+1][j] + A[i][j+1] + A[i+1][j+1].  
Recover any valid A of 0/1 entries that produces B, or report CORRUPT if none exists. H,W ≤ 300.

2. Key observations  
- Any 2×2‐sum equation links four overlapping cells. Once you fix the first row and first column of A (including A[0][0]), all other A[i][j] are determined by unwinding those sums.  
- Introduce binary variables  
    c[i] = A[i][0] for i=1…H−1,  
    r[j] = A[0][j] for j=1…W−1,  
  and try both A[0][0] = 0 or 1.  
- Define an auxiliary table δ by assuming all c[i] and r[j] are zero and propagating  
    δ[0][0] = start,  
    for i,j ≥ 1:  
      δ[i][j] = B[i−1][j−1] − δ[i−1][j] − δ[i][j−1] − δ[i−1][j−1].  
- One can show the true A[i][j] equals  
    δ[i][j] + sign_row(j)·r[j] + sign_col(i)·c[i],  
  where sign_row(j)=+1 if j even, −1 if j odd (and similarly for sign_col(i)).  
- Since A[i][j] ∈ {0,1}, any choice (c[i],r[j]) that makes this sum outside {0,1} must be forbidden. Each forbidden pair yields a 2‐SAT clause of the form  
    ¬(c[i]=ci ∧ r[j]=rj)  
  ≡ (c[i]≠ci) ∨ (r[j]≠rj).  
- We build a 2‐SAT instance on (H−1)+(W−1) variables, solve it in O(HW) time, and if satisfiable, reconstruct A; otherwise try the other start value or declare CORRUPT.

3. Full solution approach  
1. Read H,W and the (H−1)×(W−1) matrix B.  
2. For start in {0,1} (this is A[0][0]):  
   a. Build δ[H][W] with δ[0][0]=start, and for i=1…H−1, j=1…W−1:  
        δ[i][j] = B[i−1][j−1] − δ[i−1][j] − δ[i][j−1] − δ[i−1][j−1].  
      (δ on first row/col beyond (0,0) stays 0.)  
   b. Create a 2‐SAT solver with N = (H−1)+(W−1) variables:  
        variables 0…H−2 represent c[1…H−1],  
        variables H−1…H+W−3 represent r[1…W−1].  
   c. For each cell (i,j) with i,j ≥ 1 and for each assignment ci∈{0,1}, rj∈{0,1}:  
        compute val = δ[i][j] + (j%2==0 ?  rj : −rj) + (i%2==0 ?  ci : −ci).  
        If val∉{0,1}, forbid (c[i]=ci ∧ r[j]=rj) by adding the 2‐SAT clause  
           (c[i]≠ci) ∨ (r[j]≠rj).  
   d. Solve the 2‐SAT instance via SCC (Kosaraju or Tarjan).  
      If satisfiable, read out c[i], r[j], reconstruct full A:  
         A[0][0]=start,  
         A[i][0]=c[i] for i≥1,  
         A[0][j]=r[j] for j≥1,  
         A[i][j]=B[i−1][j−1]−A[i−1][j]−A[i][j−1]−A[i−1][j−1] for i,j≥1.  
      Output A and terminate.  
3. If both start values fail, print CORRUPT.

4. C++ implementation with detailed comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

// 2-SAT via implication graph + Kosaraju's SCC
struct TwoSat {
    int n;                         // number of boolean variables
    vector<vector<int>> adj, radj; // forward and reverse implication graphs
    vector<int> comp, order;
    vector<bool> used;

    TwoSat(int vars=0) { init(vars); }

    void init(int vars) {
        n = vars;
        adj.assign(2*n, {});
        radj.assign(2*n, {});
        used.assign(2*n, false);
        comp.assign(2*n, -1);
        order.clear();
    }

    // add implication: (x is f) => (y is g)
    void addImp(int x, bool f, int y, bool g) {
        int u = 2*x + (f?1:0);
        int v = 2*y + (g?1:0);
        adj[u].push_back(v);
        radj[v].push_back(u);
    }

    // add clause: (x is f) OR (y is g)
    void addOr(int x, bool f, int y, bool g) {
        // ≡ (¬(x=f) => (y=g)) and (¬(y=g) => (x=f))
        addImp(x, !f, y, g);
        addImp(y, !g, x, f);
    }

    // first DFS pass for ordering
    void dfs1(int u) {
        used[u] = true;
        for(int v: adj[u])
            if(!used[v]) dfs1(v);
        order.push_back(u);
    }
    // second DFS pass for assigning components
    void dfs2(int u, int cid) {
        comp[u] = cid;
        for(int v: radj[u])
            if(comp[v] < 0) dfs2(v, cid);
    }

    // solve 2-SAT: return (isSat, assignment)
    pair<bool, vector<bool>> solve() {
        // 1) order vertices by finish time
        for(int i = 0; i < 2*n; i++)
            if(!used[i]) dfs1(i);
        // 2) build reverse-topological by component
        int cid = 0;
        for(int i = 2*n-1; i >= 0; i--) {
            int u = order[i];
            if(comp[u] < 0)
                dfs2(u, cid++);
        }
        // 3) check conflicts and extract assignment
        vector<bool> res(n);
        for(int i = 0; i < n; i++) {
            if(comp[2*i] == comp[2*i+1])
                return {false, {}};
            // variable i is true if comp[false-literal] < comp[true-literal]
            res[i] = comp[2*i] < comp[2*i+1];
        }
        return {true, res};
    }
};

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

    int H, W;
    cin >> H >> W;
    vector<vector<int>> B(H-1, vector<int>(W-1));
    for(int i = 0; i < H-1; i++){
        string s; cin >> s;
        for(int j = 0; j < W-1; j++)
            B[i][j] = s[j] - '0';
    }

    // We'll try both A[0][0] = 0 or 1
    for(int start = 0; start < 2; start++){
        // Step A: build delta table
        vector<vector<int>> delta(H, vector<int>(W, 0));
        delta[0][0] = start;
        for(int i = 1; i < H; i++){
            for(int j = 1; j < W; j++){
                delta[i][j] = B[i-1][j-1]
                            - delta[i-1][j]
                            - delta[i][j-1]
                            - delta[i-1][j-1];
            }
        }

        // Step B: set up 2-SAT on (H-1)+(W-1) vars
        int varC = H-1, varR = W-1;
        TwoSat solver(varC + varR);

        // Step C: for each interior cell, forbid bad (c[i],r[j])
        for(int i = 1; i < H; i++){
            for(int j = 1; j < W; j++){
                for(int ci = 0; ci < 2; ci++){
                    for(int rj = 0; rj < 2; rj++){
                        int val = delta[i][j];
                        // apply sign depending on parity
                        val += (j%2==0 ?  rj : -rj);
                        val += (i%2==0 ?  ci : -ci);
                        if(val < 0 || val > 1){
                            // forbid c[i]=ci AND r[j]=rj
                            int idxC = i-1;
                            int idxR = varC + (j-1);
                            // clause: (c[i]!=ci) OR (r[j]!=rj)
                            solver.addOr(idxC, !ci, idxR, !rj);
                        }
                    }
                }
            }
        }

        // Step D: solve 2-SAT
        auto [ok, assign] = solver.solve();
        if(!ok) continue;  // try other start

        // reconstruct A
        vector<vector<int>> A(H, vector<int>(W));
        A[0][0] = start;
        // first col
        for(int i = 1; i < H; i++)
            A[i][0] = assign[i-1];
        // first row
        for(int j = 1; j < W; j++)
            A[0][j] = assign[varC + (j-1)];
        // rest by fingerprint equation
        for(int i = 1; i < H; i++){
            for(int j = 1; j < W; j++){
                A[i][j] = B[i-1][j-1]
                        - A[i-1][j]
                        - A[i][j-1]
                        - A[i-1][j-1];
                // must be 0 or 1
                assert(A[i][j] == 0 || A[i][j] == 1);
            }
        }

        // output solution
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++)
                cout << A[i][j];
            cout << "\n";
        }
        return 0;
    }

    // no valid key found
    cout << "CORRUPT\n";
    return 0;
}
```

5. Python implementation with detailed comments  
```python
import sys
sys.setrecursionlimit(10**7)

# Simple 2-SAT via Kosaraju's SCC
class TwoSat:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(2*n)]
        self.radj = [[] for _ in range(2*n)]
    def add_imp(self, x, f, y, g):
        # (x == f) => (y == g)
        u = 2*x + (1 if f else 0)
        v = 2*y + (1 if g else 0)
        self.adj[u].append(v)
        self.radj[v].append(u)
    def add_or(self, x, f, y, g):
        # (x==f) OR (y==g)
        # ≡ (¬(x==f) => (y==g)) and (¬(y==g) => (x==f))
        self.add_imp(x, not f, y, g)
        self.add_imp(y, not g, x, f)
    def solve(self):
        n2 = 2*self.n
        used = [False]*n2
        order = []
        def dfs1(u):
            used[u] = True
            for v in self.adj[u]:
                if not used[v]: dfs1(v)
            order.append(u)
        for u in range(n2):
            if not used[u]: dfs1(u)
        comp = [-1]*n2
        cid = 0
        def dfs2(u):
            comp[u] = cid
            for v in self.radj[u]:
                if comp[v] < 0: dfs2(v)
        for u in reversed(order):
            if comp[u] < 0:
                dfs2(u)
                cid += 1
        res = [False]*self.n
        for i in range(self.n):
            if comp[2*i] == comp[2*i+1]:
                return None
            # literal false < true in topo order means var is assigned that value
            res[i] = (comp[2*i] < comp[2*i+1])
        return res

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    B = [list(map(int, list(input().strip()))) for _ in range(H-1)]

    # Try both values for A[0][0]
    for start in (0,1):
        # Build delta table
        delta = [[0]*W for _ in range(H)]
        delta[0][0] = start
        for i in range(1, H):
            for j in range(1, W):
                delta[i][j] = (B[i-1][j-1]
                               - delta[i-1][j]
                               - delta[i][j-1]
                               - delta[i-1][j-1])
        # set up 2-SAT
        varC = H-1
        varR = W-1
        ts = TwoSat(varC + varR)
        # forbid bad assignments
        for i in range(1, H):
            for j in range(1, W):
                for ci in (0,1):
                    for rj in (0,1):
                        val = delta[i][j]
                        val += ( rj if j%2==0 else -rj )
                        val += ( ci if i%2==0 else -ci )
                        if val not in (0,1):
                            idxC = i-1
                            idxR = varC + (j-1)
                            # clause: (c[i] != ci) OR (r[j] != rj)
                            ts.add_or(idxC, ci^1, idxR, rj^1)
        assign = ts.solve()
        if assign is None:
            continue  # unsatisfiable, try other start

        # reconstruct A
        A = [[0]*W for _ in range(H)]
        A[0][0] = start
        for i in range(1, H):
            A[i][0] = assign[i-1]
        for j in range(1, W):
            A[0][j] = assign[varC + (j-1)]
        for i in range(1, H):
            for j in range(1, W):
                A[i][j] = (B[i-1][j-1]
                           - A[i-1][j]
                           - A[i][j-1]
                           - A[i-1][j-1])
        # output
        out = sys.stdout.write
        for row in A:
            out("".join(map(str,row)) + "\n")
        return

    # no solution found
    print("CORRUPT")

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

Explanation of main steps:  
- We unwind the fingerprint by a recurrence (`delta`) that ignores the unknown first row/column.  
- The true A[i][j] differs from δ[i][j] by a sign‐alternating sum of the row‐var and col‐var.  
- Every non‐binary result forces a 2‐SAT clause forbidding that pair of assignments.  
- A single 2‐SAT run (per choice of A[0][0]) suffices to either reconstruct A or establish CORRUPT.