50133. Word Merge Sort

I'm a slow walker, but I never walk backwards.

Task Description

You want to merge N strings in a special format. In this special string format three consecutive characters forms a word, and words are in increasing order alphabetically. The following figure shows you one string and the words in it. Note that the characters in word do not need to be arranged. Note that "afg" is "less" than "azk", which is "less" than "cpo", and so on.

samplesample

Two strings of increasingly "bigger" words can be merged into one just like a sequence of integers that we did before. For example, if we merge "afgazkcpofmnkijmnn" with "bpgbzzlol", then we get "afgazkbpgbzzcpofmnkijlolmnn".

You need to write a program to merge the strings one by one. For example, if you have three strings, first you merge the first string with the second string. Then you merge the result with the third string, and so on. After every merge, print the result string. That is, if you are given three string, you need to print two result strings. The first result string is from merging the first and second string, and the second result strings is from merging the first result string with the third string.

samplesample

Input Format

Every line of the input is a string. You need to read them until EOF. The length of every string is a multiple of $3$.

  • Number of strings >= $2$
  • Sum of lengths of all the strings < $100,000$

Output Format

Outputs are all the results of merge. If you are given $k$ strings, you need to output $k-1$ strings.

Subtasks

  • 10 points: There are exactly two strings and both strings contain exactly three characters.
  • 30 points: There are only two strings.
  • 60 points: There could be a lot of strings.

Sample Input1

spp
hyn

Sample Output1

hynspp

Sample Input2

dcvgawgazhjjpam
bncgaarfk

Sample Output2

bncdcvgaagawgazhjjpamrfk

Sample Input3

cvcrtksos
dyusky
plksdd
boubxzleotou

Sample Output3

cvcdyurtkskysos
cvcdyuplkrtksddskysos
boubxzcvcdyuleoplkrtksddskysostou

Discussion