Encryption System

時間制限 : 8 sec, メモリ制限 : 65536 KB
英語版はこちら

暗号化システム

あるプログラマーが新しい暗号化システムを開発した. しかし,そのシステムには異なる複数の文字列が同じ文字列に暗号化されてしまうという問題点があった.

彼のシステムによって暗号化された文字列が与えられる. 元の文字列を復号するため,暗号化される前の文字列の候補をすべて列挙したい. あなたの仕事はそのためのプログラムを作成することである.

小文字 a-z からなる文字列に対して,暗号化は次のステップに従って実行される.

  1. 最初に現れた 'b' を 'a' に置き換える.'b' が存在しなければ何もしない.
  2. 最初に現れた 'c' を 'b' に置き換える.'c' が存在しなければ何もしない.
  3. ...
  4. 最初に現れた 'z' を 'y' に置き換える.'z' が存在しなければ何もしない.

Input

入力は100個以下のデータセットからなる. 各データセットは1行であり,暗号化後の文字列を表す. 文字列は小文字a-zからなり,1文字以上,20文字以下である.

入力の終わりは,1つの # のみを含む行で示される.

Output

各データセットに対して 暗号化する前の文字列の候補の数 n を1行目に出力し, その後,暗号化前の文字列の候補を1行に1つずつ出力せよ. もし n が10以下であれば,候補を辞書順ですべて出力し, そうでなければ辞書順における先頭と末尾の5個ずつを辞書順で出力すること.

ここで辞書順は次のように再帰的に定義される. 空文字列は辞書順で最初に現れる. 2つの空でない文字列 x = x1 ... xky = y1 ... yl について, 文字列 x が辞書順で文字列 y より前であるとは,以下を満たすことをいう.

  • x1y1 よりアルファベット順 ('a'から'z') で前である.または
  • x1y1 が同じ文字であり x2 ... xky2 ... yl よりも辞書順で前に現れる

ことをいう.

Sample Input

enw
abc
abcdefghijklmnopqrst
z
#

Output for the Sample Input

1
fox
5
acc
acd
bbd
bcc
bcd
17711
acceeggiikkmmooqqssu
acceeggiikkmmooqqstt
acceeggiikkmmooqqstu
acceeggiikkmmooqrrtt
acceeggiikkmmooqrrtu
bcdefghijklmnopqrrtt
bcdefghijklmnopqrrtu
bcdefghijklmnopqrssu
bcdefghijklmnopqrstt
bcdefghijklmnopqrstu
0

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2014-07-11
http://icpc.iisf.or.jp/2014-waseda/