Problem Description

Mirko has created a wonderful crossword puzzle, and now he wants to put a frame around it.

Mirko’s crossword can be seen as an $m\times n$ grid, where each cell contains a lowercase letter. He wants the widths of the top, left, right, and bottom parts of the frame to be $u,l,r,d$, respectively. The frame is also divided into grid cells, and each such cell is either # or .. He also wants that if the frame is extended over the entire crossword, then the top-left cell must be #, and adjacent cells must not contain the same character. Of course, if a cell originally belongs to the crossword, then when making the final framed puzzle, the original letter in that crossword cell must be kept, not # or ..

Now, please help Mirko produce the final characters in all cells of the framed crossword.

If you cannot understand the statement well, please refer to the sample of this problem.

Input Format

The first line contains two integers $m,n$, representing the number of rows and columns.
The second line contains four integers $u,l,r,d$, representing the widths of the top, left, right, and bottom parts of the frame.
Then follow $m$ lines, each containing $n$ characters, describing all characters in the crossword grid.

Output Format

Output $u+m+d$ lines, each containing $l+n+r$ characters, representing all characters in the framed crossword.

4 4
2 2 2 2
honi
oker
nera
irak

#.#.#.#.
.#.#.#.#
#.honi#.
.#oker.#
#.nera#.
.#irak.#
#.#.#.#.
.#.#.#.#

2 4
1 0 3 1
rima
mama

#.#.#.#
rima.#.
mama#.#
.#.#.#.

Hint

Constraints

For all testdata, $1\leqslant m,n\leqslant 10$, $0\leqslant u,l,r,d\leqslant 5$.

Source

This problem is from COCI 2013-2014 CONTEST 3 T2 OKVIR, and according to the original testdata configuration, the full score is $80$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5