A - エンド・オブ・ビギニング 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

実装難易度★☆☆☆☆
謎解き難易度★★☆☆☆

問題文

ここはとある剣と魔法の世界。
数百年前、世界征服を企む魔王が伝説の勇者によって倒され、平和な時が流れていた。

数年前、ある古城の図書館から魔王が復活するという予言が記された古文書が見つかった。
しかし、魔王がどこに現れるかを記したページだけ暗号化されており、
誰も解読することができなかった。

暗号を解読し、魔王がどこに現れるのか解き明かせ。

MIDDLE OF CHAOS
BEGINNING OF LEGEND
END OF PEACE
BEGINNING OF FINALE
END OF BEGINNING
MIDDLE OF WAR
BEGINNING OF RUIN
BEGINNING OF DESTRUCTION

入力

入力は以下の形式で標準入力から与えられる。 
N
P_1 Q_1 R_1
P_2 Q_2 R_2
...
P_N Q_N R_N
  • 1 行目には暗号化されたページの行数 N (1 ≦ N ≦ 10,000) が与えられる。
  • 2 行目からの N 行のうち i 行目には暗号化されたページの i 行目の内容 P_i、 Q_i、 R_i が与えられる。
    • P_i は BEGINNING MIDDLE END のいずれかである。
    • Q_i は OF である。
    • R_i は大文字英アルファベットからなる文字列である。
    • R_i の長さ |R_i| は 1 ≦ |R_i| ≦ 20 を満たす。
    • P_i が MIDDLE の場合、 |R_i| が奇数であることが保証される。

出力

魔王がどこに現れるのか 1 行に出力せよ。
出力の末尾に改行を入れること。

入力例 1

8
MIDDLE OF CHAOS
BEGINNING OF LEGEND
END OF PEACE
BEGINNING OF FINALE
END OF BEGINNING
MIDDLE OF WAR
BEGINNING OF RUIN
BEGINNING OF DESTRUCTION

出力例 1

ALEFGARD

入力例 2

3
BEGINNING OF ATCODER
MIDDLE OF ATCODER
END OF ATCODER

出力例 2

AOR