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 は一例である.