Internet Problem Solving Contest

Problem A – Avoiding accidents

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.

Problem specification

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:

• In the easy subproblem A1 you have to produce a string of length n = 42.
• In the hard subproblem A2 you have to produce a string of length n = 39.

Input specification

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`).

Output specification

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.

What to submit

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.

Example

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 AAAA``````

If n were 29, this would be one possible correct output:

Output:

``````INTERNETPROBLEMSOLVINGCONTEST
AAAAAAAAAAAAAAAAAAAHELLOWORLD``````