27321번 - UMR의 테트리스 플레이 분석하기

문제

당신은 테트리스 마스터 UMR의 플레이를 따라하기 위해 UMR의 테트리스 플레이 영상을 분석하고 있다.

테트리스의 규칙은 다음과 같다.

• 게임은 세로 $H$칸, 가로 $W$칸의 사각 격자 공간 내에서 이루어진다. 이 공간을 “필드”라고 한다.
• 단위 정사각형 블록 4ドル$ 개로 이루어진 여러 개의 테트로미노가 순서대로 주어지고, 플레이어는 테트로미노를 조작해서 필드 내의 원하는 곳에 놓는다.
• 이때, 테트로미노는 회전할 수 있으나 뒤집을 수는 없다. 또한, 현재 필드 내에 있는 블록과 겹치는 곳에 놓을 수는 없으며, 테트로미노를 “공중에” 놓을 수도 없다. 다시 말해, 테트로미노를 한 칸 아래로 이동해도 필드를 벗어나거나 기존 블록과 겹치지 않는다면 그 곳에는 놓을 수 없다.
• 어떤 테트로미노를 놓은 후에, 완전히 블록으로 가득 찬 가로줄은 모두 지워지고, 해당 가로줄 위쪽에 위치한 블록들이 아래로 이동한다. 이 때 지워진 가로줄의 수만큼 필드의 맨 위쪽에 비어있는 가로줄이 생긴다.

테트로미노는 다음과 같이 7ドル$종류가 있으며, 왼쪽부터 순서대로 I, J, L, O, S, T, Z라고 부른다. 테트로미노를 뒤집을 수 없기 때문에 J와 L, S와 Z는 서로 다른 테트로미노이다.

당신은 영상을 분석하던 중, UMR의 플레이가 너무 빨라서 어떤 테트로미노를 놓기 전의 장면과 후의 장면만 찍힌 부분을 발견했다. 그 사이에 지나간 테트로미노는 과연 무엇이었을까?

이 문제에서는 테트로미노를 조작해서 원하는 곳으로 이동하는 과정은 무시하고, 위에서 제시한 조건에 맞는 곳이라면 어디든지 놓을 수 있다고 가정한다. (예제 3 참조)

입력

첫 번째 줄에 필드의 세로 크기 $H$와 가로 크기 $W$가 공백으로 구분되어 주어진다. (5ドル\le H\le 100,000円,ドル 5ドル\le W\le 10$)

다음 $H$개의 줄에 어떤 테트로미노를 놓기 전의 필드의 상태가 주어진다. 각각의 칸에 대해 블록이 있으면 #, 없으면 .으로 주어지며, #로만 이루어진 가로줄이 포함된 입력은 주어지지 않는다.

그다음 $H$개의 줄에 테트로미노를 놓은 후의 필드의 상태가 같은 형식으로 주어진다.

출력

7ドル$가지 테트로미노 I, J, L, O, S, T, Z 중에서 가능한 종류를 출력한다. 가능한 종류가 여러 개라면 모든 가능한 종류를 알파벳 순으로 공백 없이 출력한다. 가능한 종류가 없다면 X를 출력한다.

제한

힌트