Problem Description

Given a string $ S $, which is a concatenation of one or more words without any spaces in between. Each word is at least 2 characters long, with only the first and last characters being uppercase letters, and all other characters being lowercase letters.

Write a program that sorts these words lexicographically (ignoring case differences), and concatenates them in the same manner for output.

For example, let $ S = $ FisHDoGCaTAAAaAAbCAC. This is a concatenation of the words FisH, DoG, CaT, AA, AaA, AbC, AC. Sorting these lexicographically results in AA, AaA, AbC, AC, CaT, DoG, FisH, so the output should be AAAaAAbCACCaTDoGFisH.

Input Format

The input is given from the standard input in the following format:

$ S $

Output Format

Output the string as instructed in the problem statement.

Sample Input and Output

Sample Input #1

FisHDoGCaTAAAaAAbCAC

Sample Output #1

AAAaAAbCACCaTDoGFisH

Sample Input #2

AAAAAjhfgaBCsahdfakGZsZGdEAA

Sample Output #2

AAAAAAAjhfgaBCsahdfakGGdEZsZ

Notes/Hints

Constraints

• $ S $ is a string of length between $ 2 $ and $ 100,000 $ inclusive.
• Each character in $ S $ is either an uppercase or lowercase English letter.
• $ S $ is a concatenation of words as described in the problem statement.

Sample Explanation 1

This is the example used in the problem statement.

Sample Explanation 2

Note that there might be multiple occurrences of the same word.

见题面 Input 部分

见题面 Output 部分