시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 6 5 3 75.000%

문제

One of the most time-saving operations when drawing on a computer (for example using Photoshop) is the “bucket fill”  operation.

When you select this tool and click on a (target) pixel of the image it will fill all the pixels that have the same color than the target pixel and are connected to it. Two pixels are connected if they share a side or if they are connected through a path of connected pixels.

Let’s see an example: In the following image, if we select the “fill” operation in an image editor program and click on the center of the image (orange pixel). The whole region will be painted orange. Notice that the pixels are not connected diagonally so two corners of the image remain white.

 

Your task is: Given a matrix of digits representing the pixels, simulated what would be the result of a “fill” operation on given pixels. Thus, the colors will be represented with a number from 0 to 9.

Let’s see another example, now using digits instead of pixels. We have the following image:

0000000
0111000
0111010
0000000

If we “fill” at position Y = 0, X = 0 with color 3, all the 0s get painted of color 3. Because all of them are recursively connected.

The result will be:

3333333
3111333
3111313
3333333

입력

The first line will contain two integers R and C representing the number of rows and columns of the image.

The next R lines will contain C digits each representing the initial colors of the pixels.

The last line will contain 3 integers Y, X and K representing the row and column where we want to apply the “fill” operation and the color to use.

The images will be smaller than 1000 x 1000 pixels.

The colors are limited to a single digit from 0 to 9.

출력

Print the resulting image after applying the operation in the same format as the input.

예제 입력

4 7
0000000
0111000
0111010
0000000
0 0 3

예제 출력

3333333
3111333
3111313
3333333

예제 입력 2

9 9
000000000
011101110
011101110
011011110
000111000
011110110
011101110
011101110
000000000
4 4 2

예제 출력 2

000000000
011102220
011102220
011022220
000222000
022220110
022201110
022201110
000000000

힌트