最近,Vladik 发现了一种新的娱乐——社交网络编码机器人。他想在他的机器人中使用机器学习,所以现在他想为它们准备一些学习数据。
首先,他需要下载t个聊天记录。弗拉迪克(Vladik)编写了一个应该下载聊天记录的脚本,但是出了问题。特别是,有些消息没有发送者的信息。众所周知,如果一个人连续发送多条消息,它们都会合并为一条消息。这意味着同一发件人不能连续存在两条或更多条消息。此外,发件人绝不会在消息中提及自己。
Vladik 希望恢复所有消息的发件人,以便每两条相邻消息都有不同的发件人,并且没有发件人会在消息中提及自己。
他不知道如何执行此操作,并向您寻求帮助。帮助 Vladik 恢复每个聊天中的发件人!
输入
第一行包含单个整数 t (1 ≤ t ≤ 10) — 聊天数量。 t 聊天如下。每个聊天都按以下格式给出。
每个聊天描述的第一行包含单个整数 n (1 ≤ n ≤ 100) — 聊天中的用户数量。
下一行包含 n 个以空格分隔的不同用户名。每个用户名由小写和大写英文字母和数字组成。用户名不能以数字开头。两个用户名是不同的,即使它们仅字母大小写不同。用户名长度为正数且不超过10个字符。
下一行包含单个整数 m (1 ≤ m ≤ 100) — 聊天中的消息数。接下来的 m 行包含以下格式的消息,每行一条:
- <用户名>:<文本> — 已知发件人的消息格式。用户名应出现在聊天的用户名列表中。
- <?>:<text> — 发件人未知的消息格式。
消息正文可以由大小写英文字母、数字、字符“.”组成(点), ',' (逗号), '!' (感叹号), '?' (问号)和“ ”(空格)。文本不包含尾随空格。文本长度为正数且不超过 100 个字符。
如果用户的用户名作为单词出现在文本中,我们就说文本提及了该用户。换句话说,用户名出现的位置,其出现前后的两个字符要么不存在,要么不是英文字母或数字。例如,文本“Vasya、masha13 和 Kate!”可以提及用户“Vasya”、“masha13”、“and”和“Kate”,但不能提及“masha”。
保证在每个聊天中没有已知发件人在其消息中提及自己,并且不存在具有同一已知发件人的两条相邻消息。
输出
按以下格式打印有关 t 聊天的信息:
如果无法恢复发件人,请为此聊天打印单行“Impossible”。否则按以下格式打印 m 条消息:
<用户名>:<文本>
如果有多个答案,请打印其中任何一个。
示例
输入 #1
1 2 Vladik netman 2 ?: Hello, Vladik! ?: Hi
输出 #1
netman: Hello, Vladik! Vladik: Hi
输入 #2
1 2 netman vladik 3 netman:how are you? ?:wrong message vladik:im fine
输出 #2
Impossible
输入 #3
2 3 netman vladik Fedosik 2 ?: users are netman, vladik, Fedosik vladik: something wrong with this chat 4 netman tigerrrrr banany2001 klinchuh 4 ?: tigerrrrr, banany2001, klinchuh, my favourite team ever, are you ready? klinchuh: yes, coach! ?: yes, netman banany2001: yes of course.
输出 #3
Impossible netman: tigerrrrr, banany2001, klinchuh, my favourite team ever, are you ready? klinchuh: yes, coach! tigerrrrr: yes, netman banany2001: yes of course.