C. Владик и чат
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Владик нашел себе новое увлечение — написание ботов для социальных сетей. Ботов он хочет писать не простых, а с использованием машинного обучения. Поэтому он собрался обучать ботов на данных.

Первым делом он решил выкачать 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
2
Vladik netman
2
?: Hello, Vladik!
?: Hi
Выходные данные
netman: Hello, Vladik!
Vladik: Hi
Входные данные
1
2
netman vladik
3
netman:how are you?
?:wrong message
vladik:im fine
Выходные данные
Impossible
Входные данные
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.