AT_yuha_c88_a エンド・オブ・ビギニング

[problemUrl]: https://atcoder.jp/contests/yuha-c88/tasks/yuha_c88_a ここはとある剣と魔法の世界。 数百年前、世界征服を企む魔王が伝説の勇者によって倒され、平和な時が流れていた。 数年前、ある古城の図書館から魔王が復活するという予言が記された古文書が見つかった。 しかし、魔王がどこに現れるかを記したページだけ暗号化されており、 誰も解読することができなかった。 暗号を解読し、魔王がどこに現れるのか解き明かせ。 *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 $ 行に出力せよ。 出力の末尾に改行を入れること。 ``` 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 ``` ``` ALEFGARD ``` ``` 3 BEGINNING OF ATCODER MIDDLE OF ATCODER END OF ATCODER ``` ``` AOR ```

N/A

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 行に出力せよ。 出力の末尾に改行を入れること。