P7534 [COCI 2016/2017 #4] Kartomat

When using an automatic ticket machine at a railway station, you can search for the destination city using the keyboard shown on its screen. The keyboard can be seen as a $4 \times 8$ character matrix:  Currently, the screen shows $N$ strings, which are city names. To search for the destination city, you click several letters in order, forming an initial string. After entering the initial string, the screen will keep only the cities whose names start with that string (i.e., the remaining cities have the initial string as a prefix). Also, if the initial string plus some letter cannot match the prefix of any city, then that letter on the keyboard will be replaced by the character $\texttt{*}$. Find the final state of the keyboard after entering the initial string.

The first line contains an integer $N$, the number of cities shown on the screen. The next $N$ lines each contain a string consisting only of uppercase letters, representing a city name. Each string has length at most $100$. The last line contains the initial string. The initial string will not be exactly the same as any city name, and it is guaranteed to be a prefix of at least one city.

Output a $4 \times 8$ character matrix, representing the final state of the keyboard.

**[Sample 1 Explanation]** After entering the initial string $\texttt{ZA}$, the only remaining letters on the keyboard are $\texttt{B, D, G}$. |Initial string|Remaining letter|New string|Searchable city| | :----------: | :----------: | :----------: | :----------: | |$\texttt{ZA}$|$\texttt B$|$\texttt{ZAB}$|$\texttt{ZABOK}$| |$\texttt{ZA}$|$\texttt D$|$\texttt{ZAD}$|$\texttt{ZADAR}$| |$\texttt{ZA}$|$\texttt G$|$\texttt{ZAG}$|$\texttt{ZAGREB}$| The new strings formed by the initial string with other letters cannot be used to search for any other city, so those letters will disappear from the screen and become the character $\texttt{*}$. **[Constraints]** For $100\%$ of the testdata, $1 \le N \le 50$. **[Notes]** **Translated from [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #4](https://hsin.hr/coci/archive/2016_2017/contest4_tasks.pdf) _T2 Kartomat_.** **The score of this problem follows the original COCI task settings, with a full score of $80$.** Translated by ChatGPT 5