Xmas Contest 2016 夜の部

I - ISOLT


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 100

問題文

テトロミノには下図のように I, S, O, L, T5 種類がある.

うさぎは,テトロミノをいくつか持っている.うさぎはそれらのテトロミノを回転させたり裏返したりして,縦 H 行,横 W 列のマス目に沿って互いに重ならないようにすべて並べてアートを作った.このとき,テトロミノによって覆われたマスの情報は文字列の列 C によって以下のように表された.

  • C_{i,j}o であるとき,i 行目 j 列目のマスは覆われていたことを表す.
  • C_{i,j}. であるとき,i 行目 j 列目のマスは覆われていなかったことを表す.

その後,うさぎはこのアートを壁に飾ろうと持ち上げたが,その拍子にアートを崩してしまった.うさぎは慌てて散らばったテトロミノをかき集めたが,どうしても 1 つだけ見つからなかった.

現在,うさぎの手元には I テトロミノが I 個,S テトロミノが S 個,O テトロミノが O 個残っている.L テトロミノと T テトロミノは 1 つも残っていない.うさぎは,テトロミノによって覆われたマスの情報 C も覚えている.うさぎは,これらの情報から,無くしたテトロミノがどの種類であったかを推察することにした.

制約

  • 1 \leq H,\ W \leq 100
  • 0 \leq I,\ S,\ O
  • C_{i,j}o または .
  • 問題文の条件をみたすようなテトロミノの並べ方が 1 通り以上存在する.
  • 答えは一意に定まる.

部分点

  • 答えが L または T であるようなデータセットに正解した場合は,15 点が与えられる.
  • 追加制約のないデータセットに正解した場合は,上記とは別に 85 点が与えられる.

入力

入力は以下の形式で標準入力から与えられる.

H W
I S O
C_{1,1}C_{1,2}...C_{1,W}
C_{2,1}C_{2,2}...C_{2,W}
:
C_{H,1}C_{H,2}...C_{H,W}

出力

うさぎが無くしたテトロミノの種類を表す文字(I, S, O, L, T のうちのいずれか)を出力せよ.


入力例 1

4 5
1 1 1
o.ooo
ooooo
.o.oo
.oooo

出力例 1

L

うさぎの作ったアートは,例えば下図の様なものであったと考えられる.


入力例 2

5 9
1 4 2
.o.......
oooo.ooo.
oooo.oooo
ooo.ooooo
oooo.oooo

出力例 2

T

うさぎの作ったアートは,例えば下図の様なものであったと考えられる.


入力例 3

1 4
0 0 0
oooo

出力例 3

I

入力例 4

8 7
4 4 4
oooooo.
ooooooo
ooooooo
o.ooooo
ooooo.o
ooooooo
ooooooo
.oooooo

出力例 4

S

Submit提出する