Vladik and chat
Contest: Codeforces Round 390 (Div. 2)
Difficulty rating: 2200
Tags: brute force, constructive algorithms, dp, implementation, strings

Recently Vladik discovered a new entertainment — coding bots for social networks. He would like to use machine learning in his bots so now he want to prepare some learning data for them.

At first, he need to download t chats. Vladik coded a script which should have downloaded the chats, however, something went wrong. In particular, some of the messages have no information of their sender. It is known that if a person sends several messages in a row, they all are merged into a single message. It means that there could not be two or more messages in a row with the same sender. Moreover, a sender never mention himself in his messages.

Vladik wants to recover senders of all the messages so that each two neighboring messages will have different senders and no sender will mention himself in his messages.

He has no idea of how to do this, and asks you for help. Help Vladik to recover senders in each of the chats!

Input format:
The first line contains single integer t (1 ≤ t ≤ 10) — the number of chats. The t chats follow. Each chat is given in the following format.

The first line of each chat description contains single integer n (1 ≤ n ≤ 100) — the number of users in the chat.

The next line contains n space-separated distinct usernames. Each username consists of lowercase and uppercase English letters and digits. The usernames can't start with a digit. Two usernames are different even if they differ only with letters' case. The length of username is positive and doesn't exceed 10 characters.

The next line contains single integer m (1 ≤ m ≤ 100) — the number of messages in the chat. The next m line contain the messages in the following formats, one per line:

- <username>:<text> — the format of a message with known sender. The username should appear in the list of usernames of the chat.
- <?>:<text> — the format of a message with unknown sender.

The text of a message can consist of lowercase and uppercase English letter, digits, characters '.' (dot), ',' (comma), '!' (exclamation mark), '?' (question mark) and ' ' (space). The text doesn't contain trailing spaces. The length of the text is positive and doesn't exceed 100 characters.

We say that a text mention a user if his username appears in the text as a word. In other words, the username appears in a such a position that the two characters before and after its appearance either do not exist or are not English letters or digits. For example, the text "Vasya, masha13 and Kate!" can mention users "Vasya", "masha13", "and" and "Kate", but not "masha".

It is guaranteed that in each chat no known sender mention himself in his messages and there are no two neighboring messages with the same known sender.

Output format:
Print the information about the t chats in the following format:

If it is not possible to recover senders, print single line "Impossible" for this chat. Otherwise print m messages in the following format:

<username>:<text>

If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
1
2
Vladik netman
2
?: Hello, Vladik!
?: Hi

Example output:
netman: Hello, Vladik!
Vladik: Hi

Example input:
1
2
netman vladik
3
netman:how are you?
?:wrong message
vladik:im fine

Example output:
Impossible

Editorial:
Let's number users from 1 to n. Let's us know for every message users mentioned in message. Let's define arrays A and S. Ai =  index of sender of i-th message, if sender of i-th message is unknown, then Ai =  - 1. Si =  set of mentioned users in i-th message. Now for every message where sender is unknown we need to restore sender. In other words for every i, such that Ai =  - 1, we need to find number from 1 to n, such that for every j, that 1 ≤ j < n, condition Aj ≠ Aj + 1 satisfied.
This can be solved using Dynamic Programming:
DP(pref, last) = true, if over first pref messages we can restore all unknown senders, and pref-th message has sender number last, otherwise false.
There next transitions in DP:
$$(pref, last) \rightarrow (pref + 1, new)$$, where new — index of user, who send (pref + 1)-th message. new should be not equals to last and new should be not equals to every number from set Spref + 1. Also if for (pref + 1)-th message we know sender then new should be equals to Apref + 1.
Time complexity of this DP is O(N2 * M).
Also there is exist another solution. Greedy:
While we have messages with unknown sender, for every of which there is only one possible user, which can be put as sender not violating conditions described in statement, then put this user as sender. If in one moment we will have a message with zero possible users, which can be put as sender not violating conditions in statement, then we can't restore senders of messages in chat. Otherwise if every message has two or more possible users which can be senders, then we should choose any such message and put as sender any user, which is possible for this message.