Description

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.

Input Format

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 Format

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

4
ZAGREB
SISAK
ZADAR
ZABOK
ZA

****B*D*
*G******
********
********

4
SPLIT
VINKOVCI
NOVSKA
RIJEKA
VINKO

********
********
********
V*******

4
AAAABCD
AAAABCA
AAAACDE
AAAAAAA
AAAA

***ABC**
********
********
********

Hint

[Sample 1 Explanation]

After entering the initial string $\texttt{ZA}$, the only remaining letters on the keyboard are $\texttt{B, D, G}$.

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 CONTEST #4 T2 Kartomat.

The score of this problem follows the original COCI task settings, with a full score of $80$.

Translated by ChatGPT 5