A lot of puzzle variants tend to be harder than the corresponding genres. But paradoxically, just as there is a word that becomes shorter when you add two letters to it, there is a variant which makes any genre easier.

— Freddie Hand

Grammy is a puzzle master. Today, she is playing a variant of “Scrabble” puzzle — “Easy as Scrabble”.

The puzzle consists of an $n\times m$ grid. Each cell should be filled in with a capital letter, or left empty.

There are some clues outside the puzzle. The outside clue denotes the letter in the first non-empty cell from that direction. Additionally, some of the cells may contain x marks, denoting that the cell should be empty.

For example, the picture on the left illustrates an unsolved puzzle, and the picture on the right shows a solution to the puzzle.

Grammy wants to find a solution to the puzzle. Please help Grammy to find a solution, or report that no solution exists.

Input

The first line contains 2 integers $n,m$ ($1\le n,m\le1000$), denoting the number of rows and the number of columns of the grid.

The next line contains a dot (.), followed by $m$ characters $U_i$, denoting the clues above the grid, followed by a dot (.).

Each of the next $n$ lines contains a clue $L_i$, followed by $m$ characters $c_{ij}$, followed by a clue $R_i$, denoting the clue to the left of the grid, the grid cells, and the clue to the right of the grid.

The next line contains a dot (.), followed by $m$ characters $D_i$, denoting the clues below the grid, followed by a dot (.).

Each of the clues $U_i,L_i,R_i,D_i$ is either an upper case English character or a dot (.). Each of the central cells $c_{ij}$ is either an x or a dot (.).

All dots in the input means that the corresponding position is empty.

Output

If the solution does not exist, output NO on a single line.

Otherwise, output YES on the first line, then output $n$ lines, each containing $m$ characters, denoting a solution to the puzzle. Each empty cell should be represented by a dot. If there are multiple solutions, output any.

Please note that you should replace the given x characters in the central cells by a dot.

Please also note that you should not output the clue cells.

Examples

Input 1

5 5
.CBA...
....x..
..x...C
A.....B
B..x..A
C......
.......

Output 1

YES
CBA..
A.B.C
.A.CB
BC.A.
..CBA

Input 2

1 2
....
Nx..
..O.

Output 2

NO