I - ISOLT Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

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

うさぎは，テトロミノをいくつか持っている．うさぎはそれらのテトロミノを回転させたり裏返したりして，縦 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