005 - クレヨンの並べ替え

時間制限 8 秒 / メモリ制限 256 MB / 得点 20 / x 23 /

TLE
8sec
MLE
256MB
得点
20

問題

横浜くんはケースに入ったクレヨンを持っている．クレヨンの種類は 1 文字で表され，英小文字・英大文字・数字のいずれかで表される．ケースに同じ種類のクレヨンが複数本入っていることもある．

ある日，ケースに入ったクレヨンを家族に貸したところ，種類がバラバラに並んだ状態で返却された．クレヨンをきれいに並べることが好きな横浜くんは，次に示す順番でクレヨンを並べ替えることにした．

  • 英小文字はどの英大文字よりも左に並べられ，英大文字はどの数字よりも左に並べられる
  • 英小文字の中では，アルファベット順で早いものが左に並べられる
  • 英大文字の中では，アルファベット順で早いものが左に並べられる
  • 数字の中では，数字が小さいものが左に並べられる

並べ替えたあとのクレヨンの並びを求めよ．

Input

入力は複数のデータセットからなる．各データセットは次の形式で表される．

S

各データセットは，クレヨンの並びを表した文字列 S の 1 行からなる．S の左から i 番目の文字は，左から i 番目に入っているクレヨンの種類を表す．

S の長さは 1 以上 1,000 以下であり，S は英小文字・英大文字・数字からなる文字列である．

入力の終わりは # のみからなる行で示す．データセットは 50 個以内である．

Output

各データセットに対して，並べ替えたあとのクレヨンの並びを表した文字列を 1 行で出力せよ．

Sample Input

ICPC2023YokohamaRegional
ICPCJapaneseAlumniGroup
GoodLuckForAllContestants
#

Sample Output

aaaeghiklmnoooCCIPRY0223
aaeeilmnnopprsuuACCGIJP
acdekllnnoooorsstttuACFGL