Недавно Владик нашел себе новое увлечение — написание ботов для социальных сетей. Ботов он хочет писать не простых, а с использованием машинного обучения. Поэтому он собрался обучать ботов на данных.
Первым делом он решил выкачать t чатов. Владик написал скрипт, который должен был выкачать все чаты. По каким-то неизвестным причинам переписки выкачались неполными, а точнее у некоторых сообщений оказался неизвестен отправитель. Зато известно, что если пользователь отсылал несколько сообщений подряд, то они объединялись в одно. То есть нет двух подряд сообщений в одном чате с одним и тем же автором. Ещё известно, что отправитель сообщения не упоминал себя в сообщении.
Владик хочет восстановить отправителя для каждого сообщения с неизвестным отправителем, так чтобы у любых двух последовательных сообщений одного чата были разные отправители, и никакой отправитель не упоминал бы себя в своих сообщениях.
Он не придумал как это делать, поэтому просит вас помочь ему. Помогите Владику восстановить отправителей сообщений для каждого чата!
Входные данные
В первой строке входных данных находится единственное целое число t (1 ≤ t ≤ 10) — количество выкачанных чатов. Далее задано t чатов. Каждый чат задан в следующем формате.
В первой строке каждого описания записано целое число n (1 ≤ n ≤ 100) — количество пользователей в чате.
В следующей строке находятся n различных имен пользователей разделенных пробелом. Каждое имя пользователя состоит из прописных и строчных латинских букв и цифр, причем имя не может начинаться на цифру. Два имени пользователя различаются даже тогда, когда они различаются только регистром букв. Длина имени положительна и не превышает 10 символов.
В следующей строке дано целое число m (1 ≤ m ≤ 100) — количество сообщений в чате. В следующих m строках находятся сообщения в одном из следующих форматов, по одному на строке:
- <имя отправителя>:<текст сообщения> — формат сообщения, для которого известен отправитель. Имя отправителя должно присутствовать в списке имен пользователей чата.
- <?>:<текст сообщения> — формат сообщения, для которого неизвестен отправитель.
Текст сообщения может состоять из маленьких и больших латинских букв, цифр, '.' (точка), ',' (запятая), '!' (восклицательный знак), '?' (вопросительный знак) или ' ' (пробел). Текст сообщения не содержит пробелов в конце. Длина текста сообщения положительна и не превышает 100 символов.
Определим, что значит упоминание пользователя в сообщении. Пользователь упоминается в сообщении, если он содержится в сообщении в качестве слова. Иными словами так, что соседний слева и соседний справа от имени символы либо отсутствуют либо не равны латинской букве и цифре. Например, сообщение «Vasya, masha13 and Kate!» может содержать упоминания пользователей «Vasya», «masha13», «and» и «Kate», но не «masha».
Гарантируется, что в каждом чате, заданном во входных данных, для всех известных пользователей выполняется, что пользователь не упоминает сам себя в сообщении и нет двух подряд идущих сообщений с одним и тем же известным отправителем.
Выходные данные
Во входные данные следует вывести информацию о t чатах в следующем формате:
Если нет ни одного способа восстановить неизвестных отправителей в чате, то для такого чата следует вывести «Impossible». Иначе следует вывести m сообщений в формате:
<имя отправителя>:<текст сообщения>
Если возможных ответов несколько, следует вывести любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
2
Vladik netman
2
?: Hello, Vladik!
?: Hi
|
netman: Hello, Vladik!
Vladik: Hi
|
|
2
|
1
2
netman vladik
3
netman:how are you?
?:wrong message
vladik:im fine
|
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.
|
Impossible
netman: tigerrrrr, banany2001, klinchuh, my favourite team ever, are you ready?
klinchuh: yes, coach!
tigerrrrr: yes, netman
banany2001: yes of course.
|