34100번 - └┘ 스페셜 저지

문제

$N \times M$ 크기의 격자가 주어진다. 처음에 격자의 각 칸은 막혀있거나 비어 있는 상태이다. 여러분은 1ドル \times 1$ 크기의 조각을 세 개 이어 붙여서 만든 └ 모양 블록과 ┘모양 블록을 무한히 많이 가지고 있다.

여러분은 이 블록을 격자 위에 적절히 배치하여 모든 빈칸을 블록으로 덮고자 한다. 단, 격자 위에 블록을 배치할 때는 다음 조건을 모두 만족해야 한다.

• 각 블록의 조각이 격자에 칸에 정확히 들어맞도록 배치해야 한다.
• 블록을 회전시키거나 뒤집는 것은 불가능하다.
• 블록의 전체 또는 일부가 격자를 벗어나거나 막혀있는 칸을 덮으면 안 된다.
• 격자의 빈칸은 정확히 하나의 블록에 의해서만 덮여야 한다.

조건을 만족하는 블록의 배치가 있는지 판별하고, 가능하다면 격자에 블록을 배치해 보자.

입력

첫째 줄에 테스트 케이스의 개수를 나타내는 정수 $T$가 주어진다. $(1 \leq T \leq 300\ 000)$

각 테스트 케이스의 첫째 줄에 두 정수 $N,ドル $M$이 공백으로 구분되어 주어진다. $(2 \leq N,M \leq 3\ 000)$

이후 $N$개의 줄에 걸쳐 #과 .으로만 구성된 길이 $M$의 문자열이 한 줄에 하나씩 주어진다. $i+1$번째 줄의 $j$번째 문자가 #이면 격자의 $i$행 $j$열이 막혀 있는 칸임을, .면 빈칸임을 의미한다.

모든 테스트 케이스에서 $N \times M$의 합이 3ドル\ 000^2$을 넘지 않음이 보장된다.

출력

각 테스트 케이스마다 격자에 블록을 배치할 수 있다면 └ 모양 블록을 a, ┘모양 블록을 b로 하여 격자에 블록을 배치한 모습을 출력한다. 답이 여러 개라면 그중 하나를 출력한다.

불가능하다면 -1을 출력한다.

제한

힌트