F - DoubleCamelCase Sort /

Time Limit: 2 sec / Memory Limit: 1024 MB

注意

この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

文字列 S が与えられる。これは、1 つ以上の単語を (間に空白などを挟まずに) 連結したものである。ここで、各単語は 2 文字以上であり、最初の文字と最後の文字のみが英大文字、それ以外の文字は全て英小文字である。

これらの単語を辞書順に並べ (大文字小文字の違いは無視する)、同様に連結して出力するプログラムを作成せよ。

例えば、S = FisHDoGCaTAAAaAAbCAC とする。これは FisH, DoG, CaT, AA, AaA, AbC, AC7 つの単語を連結したものである。これらを辞書順に並べると AA, AaA, AbC, AC, CaT, DoG, FisH となるため、AAAaAAbCACCaTDoGFisH と出力すればよい。

制約

  • S は長さ 2 以上 100,000 以下の文字列である。
  • S の各文字は英大文字または英小文字である。
  • S は問題文で述べたような単語の連結である。

入力

入力は以下の形式で標準入力から与えられる。

S

出力

問題文で指示された通りの文字列を出力せよ。


入力例 1

FisHDoGCaTAAAaAAbCAC

出力例 1

AAAaAAbCACCaTDoGFisH

問題文で用いた例である。


入力例 2

AAAAAjhfgaBCsahdfakGZsZGdEAA

出力例 2

AAAAAAAjhfgaBCsahdfakGGdEZsZ

同じ単語が複数個存在する可能性があることに注意せよ。

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a string S, which is a concatenation of one or more words (without any extra characters such as spaces in between). Each word here is at least two characters long. The first and last characters are uppercase, and all the other characters are lowercase.

Write a program that sorts these words in lexicographical order (ignoring the case), concatenates them in the same manner as in S, and prints it.

For example, consider the case S = FisHDoGCaTAAAaAAbCAC. This string is a concatenation of seven words: FisH, DoG, CaT, AA, AaA, AbC, and AC. We sort them in the lexicographical order: AA, AaA, AbC, AC, CaT, DoG, FisH, and print AAAaAAbCACCaTDoGFisH.

Constraints

  • S is a string of length between 2 and 100000 (inclusive).
  • Each character of S is an uppercase or lowercase English letter.
  • S is a concatenation of words as described in Problem Statement.

Input

Input is given from Standard Input in the following format:

S

Output

Print a string as specified in Problem Statement.


Sample Input 1

FisHDoGCaTAAAaAAbCAC

Sample Output 1

AAAaAAbCACCaTDoGFisH

This is the example used in Problem Statement.


Sample Input 2

AAAAAjhfgaBCsahdfakGZsZGdEAA

Sample Output 2

AAAAAAAjhfgaBCsahdfakGGdEZsZ

Note that the same word may occur multiple times.