50142. Word Merge Sort, Again

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

Task Description

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 orderDictionary 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.

Subtasks

  • 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)

0_0.dat, 0_1.dat

2
0_0.dat
0_1.dat
0.out

Sample output 1

0.out

Sample Input 2 (stdin)

1_0.dat, 1_1.dat, 1_2.dat, 1_3.dat

4
1_0.dat
1_1.dat
1_2.dat
1_3.dat
1.out

Sample output 2

1.out

Sample Input 3 (stdin)

2_0.dat, 2_1.dat, 2_2.dat

3
2_0.dat
2_1.dat
2_2.dat
2.out

Sample output 3

2.out

Discussion