题目描述
Problem Description
When using an automatic ticket machine at a train station, you can search for destination cities through the keyboard on its screen. The keyboard can be abstracted as a $4 \times 8$ character matrix:
Currently, the screen displays $N$ strings representing city names. To search for a destination city, you click several letters to form an initial string.
After entering the initial string, only cities that start with this string (i.e., cities with a prefix matching the initial string) will remain on the screen. If no city can be found by appending a letter to the initial string, a $\texttt *$ character will replace that letter on the screen.
Determine the final state of the keyboard after entering the initial string.
Input Format
The first line contains an integer $N$, the number of cities on the screen.
The next $N$ lines each contain a string consisting only of uppercase letters, representing a city name. The length of each string does not exceed $100$.
The last line contains the initial string. This string will not be identical to any city name but will be a prefix of at least one city.
Output Format
Output a $4 \times 8$ character matrix representing the final state of the keyboard.
Sample Input and Output
Sample Input #1
4
ZAGREB
SISAK
ZADAR
ZABOK
ZA
Sample Output #1
****B*D*
*G******
********
********
Sample Input #2
4
SPLIT
VINKOVCI
NOVSKA
RIJEKA
VINKO
Sample Output #2
********
********
********
V*******
Sample Input #3
4
AAAABCD
AAAABCA
AAAACDE
AAAAAAA
AAAA
Sample Output #3
***ABC**
********
********
********
Notes
[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 Letters | New String | Searchable Cities |
|---|---|---|---|
| $\texttt{ZA}$ | $\texttt B$ | $\texttt{ZAB}$ | $\texttt{ZABOK}$ |
| $\texttt{ZA}$ | $\texttt D$ | $\texttt{ZAD}$ | $\texttt{ZADAR}$ |
| $\texttt{ZA}$ | $\texttt G$ | $\texttt{ZAG}$ | $\texttt{ZAGREB}$ |
New strings formed by the initial string and other letters cannot find any other cities, so they will disappear from the screen and be replaced by $\texttt *$ characters.
[Data Range]
For $100\%$ of the data, $1 \le N \le 50$.
[Translation and Original Problem]
This problem is translated from COCI 2016-2017 CONTEST #4 T2 Kartomat.
This problem is scored according to the original COCI settings, with a maximum score of $80$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分