Little H wants to decorate his chessboard. Little H's chessboard has $n \times m$ cells, forming an $n \times m$ grid. The rows are numbered $1$ to $n$ from top to bottom, and the columns are numbered $1$ to $m$ from left to right. The intersection points of the line segments surrounding these cells are called grid points. There are $(n+1) \times (m+1)$ such grid points.

The figure below shows a $2 \times 3$ chessboard, where the black dots are grid points and the coordinates of each cell are marked at its center.

Little H's chessboard is special: in addition to the line segments connecting adjacent grid points horizontally and vertically, each cell has exactly one diagonal line connecting two grid points. There are two possible choices for this diagonal:

• Top-left to bottom-right: called N-type.
• Top-right to bottom-left: called Z-type.

We can obtain a string of length $nm$ consisting of N and Z, representing the type of each cell, in the following way: concatenate the types of each row from left to right to get a string, and then concatenate all such strings in order from the top row to the bottom row. This string is defined as the characteristic string of the chessboard.

Because he wants to decorate his chessboard, Little H wants to color each grid point with one of three colors. Little H considers a coloring scheme to be beautiful if and only if any two grid points connected by a line segment have different colors.

The figure below shows a beautiful coloring scheme, and the corresponding characteristic string is NNNZZZ.

Little H has already determined the types of some cells and has written down the corresponding string $S$, which consists of the characters N, Z, and ?, where ? represents an undetermined type.

Please determine the types of all undetermined cells such that at least one beautiful coloring scheme exists. Provide the lexicographically smallest characteristic string, or report that no solution exists.

Input

The first line contains two integers $n, m$. The second line contains a string $S$ of length $nm$, which may only contain the characters N, Z, and ?.

Output

If a solution exists, output a single line containing the lexicographically smallest characteristic string. If no solution exists, output -1.

Constraints

For all data, $1 \le n, m \le 1000$.

• Subtask 1 (10 points): $S$ does not contain ?.
• Subtask 2 (10 points): $n, m \le 4$.
• Subtask 3 (40 points): $n, m \le 50$.
• Subtask 4 (40 points): No additional constraints.

Examples

Input 1

2 3
???ZZZ

Output 1

NNNZZZ

Input 2

2 2
NZZZ

Output 2

-1