Description

小明是个爱动手的孩子，他每看到一串文字总喜欢把它们从中间拆成两半，重复的去掉，后半元素再去掉前半已有元素，然后排序输出。例如：”saffdgdf2344fdfv66”从中间切开拆成”saffdgdf2”和”344fdfv66”两部分，去掉重复，得到：”safdg2”和”34fdv6”，后半去掉前半已有元素，则得”34v6”，最后当然得到”2adfgs”和”346v”。请你为小明编写一段程序，使小明既快又准确地来拆分这些字串。

Input

一些没有间隔的字串，仅含数字和小写英文字母。长度在2~100之内。

Output

将每个字串从中间拆开，如果遇到奇数长度，则前半部分比后半部分少一个字符。然后各自去掉重复，排序，后半部分还要去掉在前半部分中出现的字符。输出一行，前半部分，空一格，后半部分。若后半部分为空，则仅输出前半部分回车。

Sample

Input

saffdgdf2344fdfv66
abcdeff111222333444555
abababababab

Output

2adfgs 346v
12abcdef 345
ab

Source: qn