설날

설날까지 며칠밖에 남지 않았고, 재현이는 가족들을 정원에 초대했다. 손님 중에는 아이들도 있다. 아이들이 더 재미있게 어울릴 수 있도록 재현이는 숨바꼭질 게임을 진행할 계획이다.

정원은 $n \times m$ 크기의 단위 칸으로 이루어진 격자이다. 일부 칸(없을 수도 있다)에는 바위가 있고, 나머지 칸은 빈칸이다. 두 칸이 변을 공유하면 이웃한다. 각 칸은 최대 4개의 이웃을 가지며, 가로 방향 두 개와 세로 방향 두 개이다.

칸은 체스판처럼 검은색 또는 흰색으로 구분할 수 있다. 왼쪽 위 칸은 검은색이고, 이웃한 두 칸은 항상 서로 다른 색이다. 칸 번호는 1부터 시작하므로 왼쪽 위 모서리 칸은 $(1, 1)$이다.

재현이는 이웃한 칸 사이에 벽을 세워 정원을 미로로 바꾸려 한다. 칸 $a$와 $b$ 사이에 벽을 세우면 두 칸은 더 이상 이웃하지 않는다. 이웃한 두 칸 사이에 벽이 없을 때에만 직접 오갈 수 있다.

미로는 다음 성질을 만족해야 한다. 빈칸으로 이루어진 임의의 두 칸 사이에는 단순 경로가 정확히 하나 있어야 한다. $a$에서 $b$로 가는 단순 경로는 빈칸의 나열로, $a$에서 시작해 $b$에서 끝나며, 같은 칸을 두 번 지나지 않고, 연속한 두 칸이 벽 없이 이웃한 칸이어야 한다.

처음에 아이들은 $(1, 1)$ 칸에 모여 게임을 시작한다. 아이는 어떤 칸이 빈칸이고, $(1, 1)$이 아니며, 이웃한 빈칸이 정확히 하나일 때에만 그 칸에 숨을 수 있다. 재현이는 검은 칸에 장미를 심어 두었으므로, 아이들이 검은 칸에 숨으면 위험하다. 따라서 아이들이 흰 칸에서만 숨을 수 있는 미로를 만들려 한다.

주어진 정원 지도를 보고 재현이가 그런 미로를 만들도록 도와야 한다.

첫 줄에 테스트케이스의 수 $t$ ($1 \le t \le 100$)가 주어진다. 이어서 여기서 설명하는 형식의 테스트케이스 $t$개가 주어진다.

각 테스트케이스의 첫 줄에는 격자의 크기를 나타내는 두 정수 $n$, $m$ ($2 \le n, m \le 20$)이 주어진다.

다음 $n$개 줄에는 공백 없이 길이 $m$인 문자열이 주어진다. 각 문자는 다음 중 하나이다.

• O: 빈칸
• X: 바위

$(1, 1)$ 칸은 빈칸임이 보장되며, 모든 빈칸은 $(1, 1)$에서 도달할 수 있다.

$t \ge 2$이면 $n \le 10$, $m \le 10$이다. 즉, $n > 10$ 또는 $m > 10$인 격자가 입력되면 그 격자가 입력의 유일한 테스트케이스이며 $t = 1$이다.

각 테스트케이스마다 다음을 출력한다.

조건을 만족하는 미로가 없으면 NO 한 줄을 출력한다.

그렇지 않으면 YES 한 줄을 출력한 뒤, 미로를 $(2n-1) \times (2m-1)$ 크기의 격자로 출력한다. 격자의 규칙은 다음과 같다. 칸 번호는 1부터 시작한다.

• 모든 $1 \le i \le n$, $1 \le j \le m$에 대해, 칸 $(i, j)$가 빈칸이면 위치 $(2i-1, 2j-1)$에 O를, 아니면 X를 출력한다.
• 모든 $1 \le i \le n$, $1 \le j \le m-1$에 대해, 이웃한 $(i, j)$와 $(i, j+1)$ 사이에 벽이 있으면 위치 $(2i-1, 2j)$에 공백을 출력한다. 벽이 없으면 공백을 제외한 출력 가능한 문자 아무것이나 출력한다.
• 모든 $1 \le i \le n-1$, $1 \le j \le m$에 대해, 이웃한 $(i, j)$와 $(i+1, j)$ 사이에 벽이 있으면 위치 $(2i, 2j-1)$에 공백을 출력한다. 벽이 없으면 공백을 제외한 출력 가능한 문자 아무것이나 출력한다.
• 모든 $1 \le i \le n-1$, $1 \le j \le m-1$에 대해, 위치 $(2i, 2j)$에는 출력 가능한 문자 아무것이나 출력한다.

출력 가능한 문자는 ASCII 코드가 $[32, 126]$ 범위에 있는 문자이며, 공백과 영숫자를 포함한다. 각 행은 정확히 $2m-1$개의 문자로 이루어져야 하며, 행 끝의 공백도 지우면 안 된다. 행은 줄바꿈 문자로 구분한다.