펜토미노

폴리오미노란 크기가 $1 \times 1$인 정사각형을 둘 이상 이어서 붙인 평면도형이며, 다음과 같은 조건을 만족해야 한다.

• 서로 다른 두 정사각형 $A$, $B$가 인접하는 것은, 두 정사각형 $A$, $B$가 겹치지 않고 한 변을 공유하는 것으로 정의된다.
• 서로 다른 두 정사각형 $A$, $B$가 연결되어 있다는 것은, $A$와 $B$가 인접하거나, $A$와 인접하면서 $B$와 연결된 또 다른 정사각형 $C$가 존재한다는 것으로 정의된다.
• 폴리오미노를 이루는 정사각형 중 임의의 서로 다른 두 정사각형을 고르면 그 둘은 서로 연결되어 있다.

펜토미노는 정사각형 $5$개를 이어 붙인 폴리오미노를 의미한다. 펜토미노는 다음과 같이 $F$, $I$, $L$, $N$, $P$, $T$, $U$, $V$, $W$, $X$, $Y$, $Z$ 모양으로 $12$가지가 있다.

F I L N P T U V W X Y Z

몽이는 크기가 $N \times M$인 직사각형 모양 보드 위에 $12$가지 펜토미노를 한 개씩 전부 놓으려고 한다. 보드는 크기가 $1 \times 1$인 정사각형 칸으로 나뉘어 있으며, 각각의 칸에는 $0$ 또는 $1$이 쓰여 있다. $0$이 쓰인 칸은 $60$개가 있다.

펜토미노를 놓을 땐 펜토미노의 각 정사각형이 반드시 보드의 한 칸을 정확하게 포함해야 하며, 펜토미노는 서로 겹칠 수 없다. 이때, 펜토미노는 $0$이 적힌 칸 위에만 놓을 수 있으며, $1$이 적힌 칸은 펜토미노가 덮을 수 없다. 또한, 각 펜토미노는 회전하거나 뒤집어서 보드에 올려놓을 수 있다.

위 조건을 만족하며 펜토미노 $12$개를 놓아 $0$이 적힌 모든 칸을 덮는 한 가지 경우를 출력하는 프로그램을 작성하시오.

첫째 줄에 보드의 세로 크기 $N$과 가로 크기 $M$이 주어진다. ($3 \le N$, $M \le 100$)

둘째 줄부터 $N$개의 줄에 걸쳐 보드에 쓰여 있는 숫자 0 또는 1이 공백으로 구분되어 주어진다. $i$번째 줄의 $j$번째 숫자는 위에서부터 $i$번째 칸, 왼쪽에서부터 $j$번째 칸에 쓰여 있는 숫자이다.

$12$가지 펜토미노를 겹치지 않게 한 개씩 놓아 0이 쓰여 있는 칸을 모두 펜토미노로 덮을 수 있는 경우의 입력만 주어진다.

첫째 줄부터 $N$개의 줄에 걸쳐 보드의 상태를 공백으로 구분하여 출력한다.

$i$번째 줄의 $j$번째 값은 위에서부터 $i$번째 칸, 왼쪽에서부터 $j$번째 칸의 상태이다. $i$번째 줄의 $j$번째 칸에는 펜토미노를 놓았다면 펜토미노의 종류를 나타내는 알파벳(F, I, L, N, P, T, U, V, W, X, Y, Z)을 출력하고, 펜토미노를 놓을 수 없는 칸이면 1을 출력한다.

만족하는 경우가 여러 가지라면 그중 아무거나 하나를 출력한다.