004 - 残像に口紅を

時間制限 2 秒 / メモリ制限 64 MB / 得点 100 / x 17 /

TLE
2sec
MLE
64MB
得点
100

問題

ハチモジ国の文豪達は，奇妙な方法で小説を書くのを好むという．第1章は，'A'から'H'までの8種類の文字を自由に使って書く．第2章では，使ってはいけない字を1文字決めて，残りの7種の文字だけで書く．第3章は，さらに1文字禁止文字を増やし，6種類の文字で書く．以下，章が終わるたびに禁止文字が増えていき，1種類の文字だけを使って書いた最終章の第8章が終わり，最後の1文字が禁止されることで小説が完成する．すなわち，ハチモジ国の小説は以下の手順に従って作られる文字列である．

  1. 'A','B','C','D','E','F','G','H' を適当な順番に並び替えて，c1, c2, ..., c8 とする．これが文字を禁じる順番である．
  2. 長さ1以上の文字列を8個作り，s1, s2, ..., s8 とする．ただし k 番目の文字列 sk に使ってよい文字は，ck, ck+1, ..., c8 の (9-k) 種類のみである（必ず全種類の文字を使う必要はないし，同じ文字を複数回使ってもよい）．
  3. s1, s2, ..., s8 をこの順で連結する．

書かれた小説だけを見て，どの順番で文字を禁じたか推測できるだろうか？上記の手順で作られた文字列 s だけが与えられた時に，文字を禁じた順番 c1, c2, ..., c8 を逆算するプログラムを作成して欲しい．複数の可能性がある場合，どれを出力してもよい．

入力

入力は 'A','B','C','D','E','F','G','H' の8種類の文字からなる長さ N の文字列である．

出力

'A','B','C','D','E','F','G','H' の8文字を，禁止された順番に並び替えて出力せよ． 複数の可能性がある場合，どれを出力してもよい．

制約

  • 8 ≤ N ≤ 64

入出力例

入力例 1

DCBAHGFE

入力例 1 に対する出力例

DCBAHGFE

8文字しかないので，第1章が'D'，第2章が'C'，…，第8章が'E'と決まる．禁止された順番の可能性は DCBAHGFE のみである．

入力例 2

EEEEAAAA

入力例 2 に対する出力例

BCDEFGHA

最初の3文字に'E'が入らず，最後が'A'のパターンはすべて可能性がある．どれを出力してもよい．BCDEFGHA は一例である．

入力例 3

DEADBEEFCAFEBABEHAHAHA

入力例 3 に対する出力例

GDCFBEHA

章の切れ目がどこかはわからないが，一番最後まで残った文字は'A'であることなど，いくつかの条件は確定する．GDCFBEHA は一例である．