Public Judge

pjudge

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

在画图软件中,你最喜欢的便是油漆桶工具。

我们将画图软件中的画布视为一个 $N \times M$ 的由像素构成的矩阵。第 $i$ 行第 $j$ 列的像素记为 $R_{i, j}$($0 \le i < N$,$0 \le j < M$,即行与列均从 $0$ 开始编号)。由于你正在使用的电脑的机能有限,因此每个像素只能是 $0 \sim 9$ 以内的整数,共 $10$ 种。

当我们在位置 $(i, j)$ 使用油漆桶工具,将其涂成颜色 $c$ 时,所有与 $(i, j)$ 联通且颜色相同的像素的颜色都将会被更改为颜色 $c$。

我们称两个像素 $A(x_a, y_a)$ 与 $B(x_b, y_b)$ 联通,当且仅当 $|x_a-x_b| + |y_a-y_b| = 1$ 且 $A, B$ 的颜色相同,或存在另一个像素 $C$,使得像素 $A, C$ 之间联通,且像素 $B,C$ 之间联通。即,两个像素联通,当且仅当存在一条路径,满足路径上任意两个相邻的像素四联通,且所有经过的像素的颜色均相同。

problem_21701_1.png

例如,在上图中对橙色位置使用油漆桶进行涂色,会将所有右图中对应的位置全部涂色。

现在,给定当前局面下的画布,你要求出,在位置 $(x, y)$ 上使用颜色 $c$ 进行油漆桶操作后画布的形态。

输入格式

输入的第一行包含两个整数 $N, M$。

接下来 $N$ 行,每行 $M$ 个字符,描述像素构成的矩阵。每个字符均为 $0 \sim 9$ 中的整数。

最后一行包含三个整数 $x, y, c$,表示进行的操作。

输出格式

输出 $N$ 行,每行 $M$ 个字符,表示操作后矩阵的形态。

样例数据

样例 1 输入

6 7
0000000
0112211
0011210
0012210
0111110
1765671
1 2 3

样例 1 输出

0000000
0332233
0033230
0032230
0333330
1765671

样例 2 输入

1 1
0
0 0 0

样例 2 输出

0

样例 3

见下发文件。

子任务

测试点编号 $N \le $ $M \le $ 特殊性质
$1 \sim 2$ $2$ $2$
$3 \sim 5$ $10$ $10$
$6 \sim 7$ $1\,000$ $1\,000$ $N = 1$ 或 $M = 1$
$8 \sim 13$ $110$ $110$
$14 \sim 20$ $1\,000$ $1\,000$

对于所有数据,$1 \le N,M \le 1\,000$,$0 \le x < N$,$0 \le y < M$,$0 \le c \le 9$。