#P16926. SGU 307 — 密码(Cipher)

SGU 307 — 密码(Cipher)

题目描述

ASN 刚刚发明了一种全新的密码系统。

密码的密钥是一个 H×WH\times W 的 0/10/1 矩阵 AA。

为了防止保存密钥时发生数据损坏,Macrosoft 的密钥管理工具会为每个密钥保存一个“指纹”矩阵 BB。指纹矩阵大小为 (H−1)×(W−1)(H-1)\times(W-1),其中每个元素等于密钥矩阵中对应 2×22\times2 子矩阵四个元素之和:

Bi,j=Ai,j+Ai+1,j+Ai,j+1+Ai+1,j+1B_{i,j}=A_{i,j}+A_{i+1,j}+A_{i,j+1}+A_{i+1,j+1}。

现在给定一个指纹矩阵,请你找出至少一个能够产生该指纹的 0/10/1 密钥矩阵。

如果不存在任何这样的密钥,则说明指纹已经损坏,需要报告这一情况。

输入格式

第一行包含两个整数 H,WH,W:

2≤H,W≤3002\le H,W\le300。

接下来 H−1H-1 行,每行包含恰好 W−1W-1 个字符,中间没有空格,用来描述指纹矩阵。

每个字符均为 0、1、2、3 或 4。

输出格式

如果存在合法密钥,输出 HH 行,每行包含 WW 个字符 0 或 1,字符之间不加空格,表示任意一个满足条件的密钥矩阵。

如果指纹已经损坏、无法由任何 0/10/1 矩阵产生,则只输出一行:

CORRUPT

样例

3 4
222
222
0110
1001
0110