P4470 [BJWC2018] Ticket Vending

A new type of automatic ticket machine has appeared at the train station in city C. When buying a ticket, the passenger first enters the destination name on the machine. There are $N$ destinations in total. As the passenger types each letter in order, the number of candidate destinations gradually decreases. On the machine screen, there is a keyboard with $4$ rows and $8$ columns, as shown in the figure below.  After each letter is entered, only the valid characters on the keyboard are selectable (depending on the remaining candidate destinations), and the other letters are replaced by the character `*`. Given the names of $N$ destinations and the characters already typed by the passenger, output the current state of the keyboard.

The first line contains an integer $N$ ($1 \leq N \leq 50$). The next $N$ lines each contain a string of uppercase English letters with length at most $100$, representing a destination. The last line contains a string with length at most $100$, representing the characters typed in order.

Output $4$ lines, each being a string of length $8$, representing the keyboard state.

Sample explanation: After typing `ZA`, the next character could be `G` (the destination could be `ZAGREB`), or `D` (the destination could be `ZADAR`), or `B` (the destination could be `ZABOK`). Translated by ChatGPT 5