J. ICPC Board
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

As an archaeologist, you have discovered a rectangular wooden board in the ruins of an ancient city. The board is divided into a grid, and each grid cell appears to have been engraved originally with one of the letters 'C', 'I', and 'P'. However, due to decay over time, some of the letters are now indistinguishable.

During your investigation, you made the following hypothesis: any square of $$$2 \times 2$$$ cells on the board originally had two 'C's, one 'I', and one 'P'.

You now want to check whether this hypothesis is consistent with the discovered board. If it is, show one possibility of the original arrangement of the letters that aligns with the hypothesis.

Input

The input contains one or more test cases. The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 500$$$), which is the number of test cases. The descriptions of the $$$t$$$ test cases follow, each in the following format.

$$$n$$$ $$$m$$$
$$$c_{1,1}\,c_{1,2}\,\cdots\,c_{1,m}$$$
$$$c_{2,1}\,c_{2,2}\,\cdots\,c_{2,m}$$$
$$$\hphantom{\ }{\vdots}$$$
$$$c_{n,1}\,c_{n,2}\,\cdots\,c_{n,m}$$$

The first line of a test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 1000,$$$ $$$2 \leq m \leq 1000$$$). They represent the number of rows and columns of the board, respectively. The next $$$n$$$ lines, each containing $$$m$$$ characters, describe the discovered board. The $$$j$$$-th character of the $$$i$$$-th line, $$$c_{i,j}$$$, is one of 'C', 'I', 'P', and '?'. If $$$c_{i,j}$$$ is 'C', 'I', or 'P', the cell in row $$$i$$$ and column $$$j$$$ is identifiable as having that letter. If $$$c_{i,j}$$$ is '?', the letter in that cell is indistinguishable.

The sum of $$$n$$$'s over all the test cases does not exceed $$$1000.$$$ The same applies to $$$m.$$$

Output

For each test case, if the hypothesis is not consistent with the discovered board, output no in a single line. Otherwise, output yes in the first line, followed by $$$n$$$ lines representing one possibility of the original arrangement of the letters that aligns with the hypothesis. Each of these $$$n$$$ lines should contain $$$m$$$ characters. The $$$j$$$-th character of the $$$i$$$-th line should be the letter in the cell in row $$$i$$$ and column $$$j$$$. If there are multiple possible arrangements, you may output any of them.

Example
Input
3
5 7
I?I?I?I
?P?P?P?
I?I?I?I
?P?P?P?
I?I?I?I
4 4
ICPC
CPCI
ICPC
CPCI
2 2
??
??
Output
yes
ICICICI
CPCPCPC
ICICICI
CPCPCPC
ICICICI
no
yes
IC
PC