# 50142. Word Merge Sort, Again

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

The task is the same as the Merge Sort. The differences is that now the strings are in files.

We have $k$ files as input and each of them contains a string. Every three characters in a string form a word, and all words are in dictionary order as they appear in the file. For example, a file may have "abcbacbae" since “abc” is less than “bac”, which is less than “bae”.

Dictionary order

The goal of the task is to merge these $k$ strings from $k$ files into a single sorted file. Note that you cannot read all $k$ strings into memory, since you will get MLE error if you do that. Instead you must read only necessary parts from the files.

Process of Merging

## Input Format

The input has only one test case. The first line is the number of input files $k$. The following $k$ lines are the names of the $k$ input files. The length of every input file is a multiple of 3. The last line has the name of the output file.

• $k\lt 20$
• The length of the name of every file is less than 20.

## Output Format

Write the merged string into the output file.

• 10 points: There are only two input files, and each file has exactly three characters.
• 20 points: There are $k$ input files, and each file has exactly three characters.
• 70 points: There are $k$ input files, and each file has at least three characters.

## Sample Input 1 (stdin)

20_0.dat0_1.dat0.out


0.out

## Sample Input 2 (stdin)

41_0.dat1_1.dat1_2.dat1_3.dat1.out


1.out

## Sample Input 3 (stdin)

32_0.dat2_1.dat2_2.dat2.out


2.out