Automatic Ticket Machine

A new type of automatic ticket vending machine has been installed at the C City train station. When buying a ticket, a passenger first inputs the destination name. There are \(N\) possible destination stations, and as the passenger types each letter one by one, the number of candidate destinations (those with a matching prefix) gradually decreases.

The ticket machine displays a keyboard with 4 rows and 8 columns. Initially, the first 26 keys (filled in row‐major order) contain the uppercase English letters from A to Z, and the remaining 6 keys are considered inactive. After each input, only those keys that correspond to valid next letters are enabled. A letter is valid if at least one of the candidate destination names has that letter immediately following the already entered prefix. All other keys will be replaced by the character * when displayed.

Your task is to output the current state of the keyboard after a given prefix has been entered. Print the keyboard as 4 rows with 8 characters in each row, where the characters in a row are separated by a single space.

The next valid letter is determined as follows. Let \(P\) be the current prefix typed by the passenger. Among all the \(N\) destination names, consider those that start with \(P\). For each candidate destination whose length is strictly greater than \(|P|\), let the character at position \(|P|+1\) be a valid option. The set of all such characters forms the valid keys. If a key’s letter is in this set then display that letter; otherwise display * for that key.

All formulas are written in \(\LaTeX\) format.

inputFormat

The input consists of multiple lines:

1. The first line contains an integer \(N\) (\(1 \leq N \leq 10^5\)), the number of destination names.
2. The following \(N\) lines each contain a non-empty string representing a destination name (composed of uppercase English letters).
3. The last line contains a string representing the prefix that the passenger has already input. This string may be empty.

outputFormat

Print the current state of the keyboard as 4 lines. Each line contains 8 characters separated by a single space. For positions corresponding to a letter in the original keyboard layout (A to Z in row-major order), if the letter is valid (i.e. it appears as the next character in at least one candidate destination name), print the letter; otherwise print *. For positions that do not originally contain a letter (i.e. the extra 6 keys), print *.

sample

3
ABC
ABD
XYZ
AB

* * C D * * * *















*</code></pre>