问题描述

小蓝最近迷上了一款名为《点亮》的谜题游戏, 游戏在一个 $n \times n$ 的格子棋盘上进行, 棋盘由黑色和白色两种格子组成, 玩家在白色格子上放置灯泡, 确保任意两个灯泡不会相互照射, 直到整个棋盘上的白色格子都被点亮（每个谜题均为唯一解)。灯泡只会往水平和垂直方向发射光线, 照亮整行和整列, 除非它的光线被黑色格子挡住。黑色格子上可能有从 $0$ 到 $4$ 的整数数字, 表示与其上下左右四个相邻的白色格子共有几个灯泡; 也可能没有数字, 这表示可以在上下左右四个相邻的白色格子处任意选择几个位置放置灯泡。游戏的目标是选择合适的位置放置灯泡, 使得整个棋盘上的白色格子都被照亮。

例如, 有一个黑色格子处数字为 $4$ , 这表示它周围必须有 $4$ 个灯泡, 需要在他的上、下、左、右处分别放置一个灯泡; 如果一个黑色格子处数字为 $2$, 它的上下左右相邻格子只有 $3$ 个格子是白色格子, 那么需要从这三个白色格子中选择两个来放置灯泡; 如果一个黑色格子没有标记数字, 且其上下左右相邻格子全是白色格子, 那么可以从这 $4$ 个白色格子中任选出 $0$ 至 $4$ 个来放置灯泡。

题目保证给出的数据是合法的, 黑色格子周围一定有位置可以放下对应数 量的灯泡。且保证所有谜题的解都是唯一的。

现在, 给出一个初始的棋盘局面, 请在上面放置好灯泡, 使得整个棋盘上的白色格子被点亮。

输入格式

输入的第一行包含一个整数 $n$, 表示棋盘的大小。

接下来 $n$ 行, 每行包含 $n$ 个字符, 表示给定的棋盘。字符. 表示对应的格 子为白色, 数字字符 0 、 1 、 2 、 3 、 4 表示一个有数字标识的黑色格子, 大写字母 $x$ 表示没有数字标识的黑色格子。

输出格式

输出 $n$ 行, 每行包含 $n$ 个字符, 表示答案。大写字母 O 表示对应的格子包含灯泡, 其它字符的意义与输入相同。

5
.....
.2.4.
..4..
.2.X.
.....

...O.
.2O4O
.O4O.
.2OX.
O....

样例说明

答案对应的棋盘布局如下图所示:

评测用例规模与约定

对于所有评测用例, $2 \leq n \leq 5$, 且棋监上至少有 15% 的格子是黑色格子。