You have a collection of four-character words on your desk. However, your friends and their little child are visiting you next week. If the toddler finds and tries to eat your words, it may choke on them and die. To prevent such an accident, you want to hide your words into a single longer string that won’t fit into the baby’s mouth.
You are given exactly ten strings. Each of them consists of exactly four characters. Construct a new string of length exactly n which contains all ten given words as substrings.
Each substring must be contiguous. For example, ABXCD does not contain ABCD as a substring. The occurrences of the ten given strings may appear in any order and they may overlap arbitrarily.
This problem has two independent subproblems:
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line. Each test case consists of exactly ten space-separated strings. Each string consists of exactly four UPPERCASE English letters (from A to Z).
For each test case, print a single line with a string of UPPERCASE letters. Each of given ten words must appear in your string as a substring at least once. The length of the string must be exactly 42 if you are solving the easy subproblem, and it must be exactly 39 if you are solving the hard subproblem.
The inputs are chosen in such a way that a solution always exists. If there are multiple solutions, you may choose and output any one of them.
Do not submit any programs. Your task is to produce and submit the correct output files a1.out and a2.out for the provided input files a1.in and a2.in. Each line in the file a1.out must contain a 42-character string. Each line in the file a2.out must contain a 39-character string.
Here is one possible input file:
Input:
2
TEST INTE RNET PROB ROBL OBLE BLEM SOLV VING TEST
AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAAIf n were 29, this would be one possible correct output:
Output:
INTERNETPROBLEMSOLVINGCONTEST
AAAAAAAAAAAAAAAAAAAHELLOWORLD