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-----

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-----

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.


-----Examples-----
Input
1
2
Vladik netman
2
?: Hello, Vladik!
?: Hi

Output
netman: Hello, Vladik!
Vladik: Hi

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

Output
Impossible

Input
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.

Output
Impossible
netman: tigerrrrr, banany2001, klinchuh, my favourite team ever, are you ready?
klinchuh: yes, coach!
tigerrrrr: yes, netman
banany2001: yes of course.

Difficulty: interview

Starter code:

Solutions:
def pr( name , lvl , dp , u , tot ): 
    if lvl == 0:
        print(name + ':' + tot[lvl])
        return

    pr( u[lvl][name] , lvl - 1 , dp , u , tot )
    print(name + ':' + tot[lvl])

def solve(): 
    n = int(input())
    users = input().split()
    m = int(input())
    dp = [] 
    u = []
    tot = [] 
    for i in range( m ) : 
        dp.append( set() ) 
        u.append( {} ) 
        line = input().split(':')
        sender = line[0]
        tot.append( line[1] ) 
        line[1] = line[1].replace( '?' , ' ' )
        line[1] = line[1].replace( '.' , ' ' )
        line[1] = line[1].replace( ',' , ' ' )
        line[1] = line[1].replace( '!' , ' ' )
        mess = line[1].split()

        if sender == '?' : 
            if i != 0:
                for name in users:
                    for x in dp[i-1]: 
                        if x != name and name not in mess:
                            dp[i].add( name ) 
                            u[i][name] = x
            else : 
                for name in users: 
                    if name not in mess:
                        dp[i].add( name ) 
        else: 
            if i != 0: 
                for x in dp[i-1]: 
                    if x != sender: 
                        dp[i].add( sender ) 
                        u[i][sender] = x
            else: 
                dp[i].add( sender )
        
        
    if dp[m-1]: 
        pr( list(dp[m-1])[0] , m-1 , dp , u , tot )
    else: 
        print("Impossible")


t = int(input())
for i in range( t ) : 
    solve()


#!/usr/bin/env python3

import re

def cont(line, user):
	return re.search('[^a-zA-Z0-9]' + user + '[^a-zA-Z0-9]', '_' + line + '_')

tests = int(input())
for test in range(tests):
	input()
	users = input().rstrip('\n').split(' ')
	linecnt = int(input())
	lines = [input().rstrip('\n') for _ in range(linecnt)]
	lines = [x.split(':', maxsplit=1) for x in lines]
	poss = [[]] * linecnt
	for i, (user, line) in enumerate(lines):
		if user != '?':
			poss[i] = [user]
		else:
			poss[i] = [u for u in users if not cont(line, u)]

	el = list(enumerate(lines))
	rel = list(reversed(el))

	changed = False
	while True:
		for i, (user, line) in el:
			if i > 0 and len(poss[i-1]) == 1:
				if poss[i-1][0] in poss[i]:
					poss[i].remove(poss[i-1][0])
					changed = True
		for i, (user, line) in rel:
			if i < linecnt - 1 and len(poss[i+1]) == 1:
				if poss[i+1][0] in poss[i]:
					poss[i].remove(poss[i+1][0])
					changed = True
		if not changed:
			break
		changed = False

	if all(len(p) > 0 for p in poss):
		for i, p, (user, line) in zip(list(range(linecnt)), poss, lines):
			if i > 0:
				if poss[i-1][0] in p:
					p.remove(poss[i-1][0])
			print(p[0] + ':' + line)
	else:
		print('Impossible')


import re
import sys


def g(cts, names):
  la = dict([(p, None) for p in names.difference(cts[0])])
  if len(la) == 0:
    return None
  d = [la]
  for i in range(1, len(cts)):
    prev = d[-1]
    la = dict()
    for p in names.difference(cts[i]):
      for n in prev.keys():
        if n != p:
          la[p] = n
          break
    if len(la) == 0:
      return None
    d.append(la)
  cur = list(d[-1].keys())[0]
  result = []
  for i in range(len(cts) - 1, -1, -1):
    result.append(cur)
    cur = d[i][cur]
  result.reverse()
  return result


def solve():
  n = int(input())
  names = input().split()
  set_names = set(names)

  def get_names(text):
    result = []
    for p in re.split("\W+", text):
      if p in set_names:
        result.append(p)
    return result

  m = int(input())
  messages = []
  for i in range(m):
    s = input()
    colon = s.find(":")
    name = s[:colon]
    text = s[colon + 1:]
    if name == "?":
      name = None
    messages.append([name, text, get_names(text)])

  for i in range(m):
    if messages[i][0]:
      continue
    j = i
    cts = []
    while j < m and not messages[j][0]:
      cts.append(set(messages[j][2]))
      j += 1
    if i > 0:
      cts[0].add(messages[i - 1][0])
    if j < m:
      cts[-1].add(messages[j][0])
    sb = g(cts, set_names)
    if not sb:
      return None
    for k in range(i, j):
      messages[k][0] = sb[k - i]

  for p in messages:
    print("%s:%s" % (p[0], p[1]))
  return True;


def main():
  tests = int(input())
  for i in range(tests):
    if not solve():
      print("Impossible")
  return 0

def __starting_point():
  return(main())
__starting_point()

def main():
    n = int(input())
    names = input().split()
    m = int(input())
    msg = [input().split(':') for _ in range(m)]
    texts = []
    for i in msg:
        texts.append(i[1])
        i[1] = i[1].replace(',', ' ').replace('.', ' ').replace('!', ' ').replace('?', ' ').split()
        if i[0] == '?':
            i.append([])
            for name in names:
                if name not in i[1]:
                    i[2].append(name)
            if len(i[2]) == 0:
                print('Impossible')
                return
    go_on = True
    while go_on:
        go_on = False
        for i in range(len(msg)):
            if msg[i][0] != '?':
                continue
            if i - 1 > -1 and msg[i - 1][0] in msg[i][2]:
                msg[i][2].remove(msg[i - 1][0])
                go_on = True
            if i + 1 < m and msg[i + 1][0] in msg[i][2]:
                msg[i][2].remove(msg[i + 1][0])
                go_on = True
            if len(msg[i][2]) == 0:
                print('Impossible')
                return
            if len(msg[i][2]) == 1:
                msg[i][0] = msg[i][2][0]
                del msg[i][2]
                go_on = True
    for i in range(len(msg)):
        if msg[i][0] == '?':
            msg[i][0] = msg[i][2][0]
            if i < m - 1 and len(msg[i + 1]) == 3 and msg[i][0] in msg[i + 1][2]:
                msg[i + 1][2].remove(msg[i][0])
        print(msg[i][0], ':', texts[i], sep='')

t = int(input())

for _ in range(t):
    main()


import sys
import re

def mentioned_usernames(line):
    return {x for x in re.split(r'[^A-Za-z0-9]+', line)}

t = int(input())

for ti in range(t):
    possible_users = []
    messages = []
    n = int(input())
    usernames = set(input().split())
    # print("usernames =", usernames, file=sys.stderr)
    m = int(input())
    for i in range(m):
        user, text = input().split(':')
        messages.append(text)
        if user == '?':
            mu = mentioned_usernames(text)
            possible_users.append(usernames - mentioned_usernames(text))
        else:
            possible_users.append({user})

    # print(possible_users, file=sys.stderr)

    is_fixed = [False] * m
    for i in range(m-1):
        if len(possible_users[i]) == 1:
            possible_users[i+1].difference_update(possible_users[i])
            is_fixed = True
    for i in range(m-1, 0, -1):
        if len(possible_users[i]) == 1:
            possible_users[i-1].difference_update(possible_users[i])
            is_fixed = True

    # print(possible_users, file=sys.stderr)

    res = []
    is_possible = True
    prev_user = '$'
    for i in range(m):
        if possible_users[i]:
            pusers = possible_users[i] - {prev_user}
            resx = next(iter(pusers))
            res.append(resx)
            prev_user = resx
        else:
            is_possible = False
            break

    if is_possible:
        for i in range(m):
            print('{}:{}'.format(res[i], messages[i]))
    else:
        print("Impossible")


def dfs(ind):
    if ind > 0:
        if possible[ind][0] in possible[ind - 1]:
            possible[ind - 1].remove(possible[ind][0])
            if len(possible[ind - 1]) == 1:
                dfs(ind - 1)
    if ind < m - 1:
        if possible[ind][0] in possible[ind + 1]:
            possible[ind + 1].remove(possible[ind][0])
            if len(possible[ind + 1]) == 1:
                dfs(ind + 1)
def Check(st, ms):
    for i in range(0, len(ms) - len(st) + 1):
        if st == ms[i:i+len(st)]:
            t = True
            if i > 0:
                if ms[i - 1] == ' ' or ms[i - 1] == '.' or ms[i - 1] == ',' or ms[i - 1] == '?' or ms[i - 1] == '!':
                    e = 0
                else:
                    t = False
            if i < len(ms) - len(st):
                if (ms[i + len(st)] == ' ' or ms[i + len(st)] == '.' or ms[i + len(st)] == ',' or ms[i + len(st)] == '?' or ms[i + len(st)] == '!'):
                    e = 0
                else:
                    t = False
            if t:
                return True
    return False
R = lambda:list(map(int, input().split(' ')))
#r, w = open("input.txt", "r"), open("output.txt", "w")
T = int(input())
while T:
    n = int(input())
    users = input().split(' ')
    m = int(input())
    possible = [[] for i in range(m)]
    sender, message = [], []
    for i in range(m):
        s = input().split(':')
        sender.append(s[0])
        message.append(s[1])
    for i in range(m):
        if sender[i] == '?':
            unallow = " "
            if i > 0 and len(possible[i - 1]) == 1:
                unallow = possible[i - 1][0]
            for j in users:
                if j == unallow:
                    continue
                done = Check(j, message[i])
                if not done:
                    possible[i].append(j)
        else:
            possible[i].append(sender[i])
    used = [0 for i in range(m)]
    for i in range(m):
        if len(possible[i]) == 1 and used[i] == 0:
            dfs(i)
    for i in range(m):
        if len(possible[i]) > 1:
            possible[i] = [possible[i][0]]
            dfs(i)
    done = False
    for i in possible:
        if len(i) == 0:
            print("Impossible")
            done = True
            break
    if not done:
        for i in range(m):
            print(possible[i][0]+':'+message[i])
    T -= 1


    



# Bartek Kostka
#  You are not prepared!

import re


def go(i):
    nonlocal counter
    counter += 1
    if counter > 2000:
        return False
    if i == len(E):
        return True
    if E[i][0] != "?":
        prop = E[i][0]
        if i == 0 or W[i-1] != prop:
            W[i] = prop
            return go(i+1)
        else:
            return False
    for pos in E[i][1]:
        if i == 0 or W[i-1] != pos:
            W[i] = pos
            if go(i+1):
                return True
    return False


t = int(input())
for ttt in range(t):
    n = int(input())
    users = input().split(" ")
    users_set = set(users)
    m = int(input())
    E = []
    S = []
    counter = 0
    W = ["" for x in range(m)]
    for mmm in range(m):
        line = input()
        (user, sentence) = line.split(":")
        S.append((user, sentence))
        words = [x.strip() for x in re.split('\W+', sentence)]
        mentions = list([x for x in words if x in users_set])
        E.append([user, set(mentions)])
    for i in range(len(E)-1):
        if E[i][0] != "?":
            E[i+1][1].add(E[i][0])
    for i in range(1, len(E)):
        if E[i][0] != "?":
            E[i-1][1].add(E[i][0])
    for i in range(len(E)):
        E[i][1] = E[i][1].symmetric_difference(users_set)
    if go(0):
        for i in range(len(E)):
            print(str(W[i])+":"+str(S[i][1]))
    else:
        print("Impossible")


import re
import copy

t = int(input())

for i in range(t):
	n = int(input())
	senderList = []
	for x in input().split():
		senderList.append(x)

	m = int(input())
	msg = [None] * m
	resSenders = [None] * m
	possibleSenders = []
	for i in range(m):
		possibleSenders.append(copy.copy(senderList))

	for i in range(m):
		line = input()
		blocks = re.findall(r"[\w]+", line)

		for x in blocks:
			try:
				possibleSenders[i].remove(x)
			except:
				pass

		if line[0] != '?':
			resSenders[i] = blocks[0]
			if i > 0:
				try:
					possibleSenders[i-1].remove(resSenders[i])
				except:
					pass
			if i+1 < m:
				try:
					possibleSenders[i+1].remove(resSenders[i])
				except:
					pass
		msg[i] = line[line.find(":")+1:]

	resolved = False
	while True:
		done = True
		justPick = True
		for i in range(m):
			if resSenders[i] != None:
				continue
			if len(possibleSenders[i]) == 0:
				done = True
				resolved = True
				print("Impossible")
				break
			if len(possibleSenders[i]) == 1:
				resSenders[i] = possibleSenders[i][0]
				if i > 0:
					try:
						possibleSenders[i-1].remove(resSenders[i])
					except:
						pass
				if i+1 < m:
					try:
						possibleSenders[i+1].remove(resSenders[i])
					except:
						pass
				justPick = False
			else:
				done = False
		if done:
			break
		if justPick:
			for i in range(m):
				if resSenders[i] == None:
					resSenders[i] = possibleSenders[i][0]
					if i+1 < m:
						try:
							possibleSenders[i+1].remove(resSenders[i])
						except:
							pass
			break

	if not resolved:
		for i in range(m):
			print(resSenders[i] + ":" + msg[i])

import re


def foo():
    n = int(input())
    who = input().split()
    m = int(input())
    msg = []

    l = []

    for num in range(m):
        a, t = input().split(':')
        msg.append(t)

        st = set()

        if a != '?':
            st.add(a)
        else:

            names = re.split('\W+', t)

            for w in who:
                if not w in names:
                    st.add(w)

        l.append(st)

    d2 = []

    for num in range(1, m):
        d = {}
        for w1 in l[num]:
            for w2 in l[num - 1]:
                if w1 != w2:
                    d[w1] = w2
                    break

        l[num] = [x for x in d]

        d2.append(d)

    curr = None

    for w in l[m - 1]:
        curr = w

    res = [curr]

    for num in list(reversed(list(range(1, m)))):
        curr = d2[num - 1].get(curr, None)  # d2[num - 1][curr]
        res.append(curr)

    res = list(reversed(res))

    if None in res:
        print("Impossible")
    else:
        for num in range(m):
            print(res[num] + ':' + msg[num])


t = int(input())

for _ in range(t):
    foo()


def main():
    n = int(input())
    names = input().split()
    m = int(input())
    msg = [input().split(':') for _ in range(m)]
    texts = []
    for i in msg:
        texts.append(i[1])
        i[1] = i[1].replace(',', ' ').replace('.', ' ').replace('!', ' ').replace('?', ' ').split()
        if i[0] == '?':
            i.append([])
            for name in names:
                if name not in i[1]:
                    i[2].append(name)
            if len(i[2]) == 0:
                print('Impossible')
                return
    go_on = True
    while go_on:
        go_on = False
        for i in range(len(msg)):
            if msg[i][0] != '?':
                continue
            if i - 1 > -1 and msg[i - 1][0] in msg[i][2]:
                msg[i][2].remove(msg[i - 1][0])
                go_on = True
            if i + 1 < m and msg[i + 1][0] in msg[i][2]:
                msg[i][2].remove(msg[i + 1][0])
                go_on = True
            if len(msg[i][2]) == 0:
                print('Impossible')
                return
            if len(msg[i][2]) == 1:
                msg[i][0] = msg[i][2][0]
                del msg[i][2]
                go_on = True
    for i in range(len(msg)):
        if msg[i][0] == '?':
            msg[i][0] = msg[i][2][0]
            if i < m - 1 and len(msg[i + 1]) == 3 and msg[i][0] in msg[i + 1][2]:
                msg[i + 1][2].remove(msg[i][0])
        print(msg[i][0], ':', texts[i], sep='')

t = int(input())

for _ in range(t):
    main()

import re

t = int(input())

delimiters = "?", ".", " ", ",", "!", ":"
regexPattern = '|'.join(map(re.escape, delimiters))

for i in range(t):
  n = int(input())
  usernames = {x for x in str.split(input(), ' ')}
  m = int(input())
  possibilities = []
  for j in range(m):
    possibilities.append({x for x in usernames})
  messages = []
  for j in range(m):
    messages.append(input())

  for j in range(m):
    if (messages[j][0] != '?'):
      messageSplit = re.split(':', messages[j])
      possibilities[j] = {messageSplit[0]}
    else:
      messageSplit = re.split(regexPattern, messages[j])
      for token in messageSplit:
        if token in usernames:
          possibilities[j] = possibilities[j] - {token}
  changed = True
  while changed:
    changed = False
    for j in range(m):
      if len(possibilities[j]) == 1:
        (poss,) = possibilities[j]
        if j < m-1 and poss in possibilities[j+1]:
          changed = True
          possibilities[j+1] = possibilities[j+1] - possibilities[j]
        if j > 0 and poss in possibilities[j-1]:
          changed = True
          possibilities[j-1] = possibilities[j-1] - possibilities[j]
  worked = True
  for j in range(m):
    if len(possibilities[j]) == 0:
      worked = False
      
  if not worked:
    print("Impossible")
  else :
    for j in range(m):
      poss = next(iter(possibilities[j]))
      if (messages[j][0] == '?'):
        print(poss + messages[j][1:])
      else:
        print(messages[j])
      if (j < m-1):
        possibilities[j+1] = possibilities[j+1] - {poss}



import re

def add_used(id, s, used):
    used[id-1].add(s)
    used[id].add(s)
    used[id+1].add(s)

tcase = int(input())
for cas in range(tcase):
    n = int(input())
    names = input().split()
    m = int(input())
    
    res = True
    ans = [''] * (m+1)
    msg = [''] * (m+1)
    used = [set() for i in range(m+1)]
    
    for i in range(m):
        ans[i], msg[i] = input().split(':')
        if ans[i] != '?':
            add_used(i, ans[i], used)
        
        mentioned = re.split('\W+', msg[i])
        for s in mentioned:
            if s in names:
                used[i].add(s)
    
    for i in range(m):
        if ans[i] == '?' and len(used[i]) == n-1:
            ans[i] = list(set(names) - used[i])[0]
            add_used(i, ans[i], used)
    
    for i in range(m):
        if ans[i] == '?':
            if len(used[i]) == n:
                res = False
            else:
                ans[i] = list(set(names) - used[i])[0]
                add_used(i, ans[i], used)
    
    for i in range(m-1):
        if ans[i] == ans[i+1]:
            res = False
    
    if res:
        for i in range(m):
            print(ans[i] + ':' + msg[i])
    else:
        print('Impossible')

from sys import stdin

t = int(stdin.readline())

def c(l,r,msg):
    f = True
    if l > 0 and not msg[l-1].isdigit() and not msg[l-1].isalpha():
        pass
    elif l == 0:
        pass
    else:
        f = False

    if r == len(msg) - 1:
        pass
    elif not msg[r+1].isdigit() and not msg[r+1].isalpha():
        pass
    else:
        f = False

    return f


def dd(i):
    if i - 1 in no_author_set:
        authors[i-1].discard(authors[i])
        if len(authors[i-1]) == 1:
            no_author_set.discard(i-1)
            for d in authors[i-1]:
                authors[i-1] = d
                break
            dd(i-1)
        if len(authors[i-1]) == 0:
            return False
    if i + 1 in no_author_set:
        authors[i+1].discard(authors[i])
        if len(authors[i+1]) == 1:
            no_author_set.discard(i+1)
            for d in authors[i+1]:
                authors[i+1] = d
                break
            dd(i+1)
        if len(authors[i-1]) == 0:
            return False
    return True

try:
    answers = []
    for i in range(t):
        ans = True
        n = int(stdin.readline())
        names = set(stdin.readline().strip().split())
        m = int(stdin.readline())
        authors = list()
        messages = list()
        no_author = list()
        no_author_set = set()
        for j in range(m):
            line = stdin.readline().strip()
            author, msg = line.split(':')
            messages.append(msg)
            if author == '?':
                no_author.append(j)
                no_author_set.add(j)
                a_set = set()
                for name in names:
                    l = msg.find(name)
                    while l != -1:
                        if c(l,l+len(name)-1, msg):
                            a_set.add(name)
                        l = msg.find(name,l+len(name))
                authors.append(names-a_set)
                if j-1 not in no_author_set:
                    authors[j].discard(authors[j-1])
            else:
                authors.append(author)
                if j - 1 in no_author_set:
                    authors[j-1].discard(author)

        for j in no_author:
            if j in no_author_set:
                if len(authors[j]) == 1:
                    no_author_set.discard(j)
                    for d in authors[j]:
                        authors[j] = d
                        break
                    if not dd(j):
                        ans = False
                elif len(authors[j]) == 0:
                    ans = False

        no_author = list()
        for j in no_author_set:
            no_author.append(j)
        no_author.sort()
        for i in no_author:
            for d in authors[i]:
                authors[i] = d
                break
            if i + 1 in no_author_set:
                authors[i+1].discard(authors[i])
        if not ans:
            answers.append('Impossible')
        else:
            for j in range(m):
                answers.append('%s:%s'%(authors[j],messages[j]))
except Exception as e:
    print(e)

for m in answers:
    print(m)

import re
t = int(input())
for _ in range(t):
    n = int(input())
    names = set(input().split())
    m = int(input())
    dp = []
    a = []
    for i in range(m): a.append(input())
    for i in range(m):
        sender, msg = a[i].split(':')
        ls = set([_f for _f in re.split('\W+',msg) if _f])
        dp.append((names if sender == '?' else set([sender])) - ls)
        if i and len(dp[i-1]) == 1: dp[i] -= dp[i-1]
        # print(dp[i]);
    if any([len(p) == 0 for p in dp]): print("Impossible")
    else:
        res = []
        for i in reversed(list(range(m))):
            res.append(dp[i].pop())
            if i > 0: dp[i-1].discard(res[-1])
        for i in range(m): 
            sender, msg = a[i].split(':')
            sender = res[m-i-1]
            print(sender+':'+msg)


import re

t = int( input() )
for z in range(t):
	n = int( input() )
	users = input().split();
	#print(users)
	m = int( input() )
	can = [ [] for i in range(m) ]
	ok = True
	L = []
	for i in range(m):
		l = input().split(':')
		#print(l)
		L += [l]
		if l[0] != '?':
			can[i] = [users.index(l[0])]
		else:
			can[i] = [x for x in range(n)]
		ll = re.sub(r'[^A-Za-z0-9]', ' ', l[1]).split()
		for j in ll:
			#print(j)
			if j in users:
				try:
					can[i].remove( users.index(j) )
				except ValueError:
					pass
		if len(can[i]) == 0:
			ok = False
	if ok == False:
		print('Impossible')
		continue
	while 1:
		flag = True
		for i in range(m - 1):
			if (len(can[i]) == 0): ok = False
			if (len(can[i]) == 1 and can[i][0] in can[i+1]):
				can[i+1].remove( can[i][0] )
				L[i][0] = users[ can[i][0] ]
				flag = False
			if (len(can[i + 1]) == 1 and can[i + 1][0] in can[i]):
				can[i].remove( can[i + 1][0] )
				L[i + 1][0] = users[ can[i + 1][0] ]
				flag = False
		if len(can[m - 1]) == 0: ok = False
		if ok == False: break
		if flag: break
	if ok == False:
		print('Impossible')
		continue
	for i in range(m):
		if L[i][0] == '?':
			print(users[ can[i][0] ], end='')
			if i < m - 1 and can[i][0] in can[i + 1]:
				can[i + 1].remove( can[i][0] )
		else:
			print(L[i][0], end='')
		print(':', L[i][1], sep = '');


3

import re

t = int(input())

for ti in range(t):
    n = int(input())
    users = set(input().split(' '))

    m = int(input())
    messages = []

    guessed = [None for i in range(m)]
    denied = [set() for i in range(m)]

    for i in range(m):
        mg = input()
        if not mg.startswith('?:'):
            guessed[i] = mg[:mg.find(':')]

        mg = mg[mg.find(':'):]
        messages.append(mg)

        m2 = mg + ' '
        for u in users:
            if re.search('[^a-zA-Z0-9]' + u + '[^a-zA-Z0-9]', m2):
                denied[i].add(u)

    answer = True

    for i in range(m):
        if guessed[i]:
            if i > 0: denied[i-1].add(guessed[i])
            if i < m-1: denied[i+1].add(guessed[i])

    for i in range(m):
        if guessed[i] in denied[i]:
            answer = False

    #print(guessed)
    #print(denied)

    changed = True
    while changed and answer:
        changed = False
        for i in range(m):
            if not guessed[i]:
                if len(users) - len(denied[i]) == 1:
                    changed = True
                    guessed[i] = (users - denied[i]).pop()
                    if i > 0: denied[i-1].add(guessed[i])
                    if i < m-1: denied[i+1].add(guessed[i])
                if len(users) == len(denied[i]):
                    answer = False
                    break

    for i in range(m):
        if not guessed[i] and len(users) - len(denied[i]) >= 1:
            guessed[i] = (users - denied[i]).pop()
            if i < m-1: denied[i+1].add(guessed[i])


    for i in guessed:
        if not i:
            answer = False

    if not answer:
        print("Impossible")
    else:
        for i in range(m):
            print(guessed[i] + messages[i])
    


import sys
import re

def mentioned_usernames(line):
    return {x for x in re.split(r'[^A-Za-z0-9]+', line)}

t = int(input())

for ti in range(t):
    possible_users = []
    messages = []
    n = int(input())
    usernames = set(input().split())
    # print("usernames =", usernames, file=sys.stderr)
    m = int(input())
    for i in range(m):
        user, text = input().split(':')
        messages.append(text)
        if user == '?':
            mu = mentioned_usernames(text)
            possible_users.append(usernames - mentioned_usernames(text))
        else:
            possible_users.append({user})

    # print(possible_users, file=sys.stderr)

    is_fixed = [False] * m
    for i in range(m-1):
        if len(possible_users[i]) == 1:
            possible_users[i+1].difference_update(possible_users[i])
            is_fixed = True
    for i in range(m-1, 0, -1):
        if len(possible_users[i]) == 1:
            possible_users[i-1].difference_update(possible_users[i])
            is_fixed = True

    # print(possible_users, file=sys.stderr)

    res = []
    is_possible = True
    prev_user = '$'
    for i in range(m):
        if possible_users[i]:
            pusers = possible_users[i] - {prev_user}
            resx = next(iter(pusers))
            res.append(resx)
            prev_user = resx
        else:
            is_possible = False
            break

    if is_possible:
        for i in range(m):
            print('{}:{}'.format(res[i], messages[i]))
    else:
        print("Impossible")


import sys
import re

def mentioned_usernames(line):
    return {x for x in re.split(r'[^A-Za-z0-9]+', line)}

t = int(input())

for ti in range(t):
    possible_users = []
    messages = []
    n = int(input())
    usernames = set(input().split())
    # print("usernames =", usernames, file=sys.stderr)
    m = int(input())
    for i in range(m):
        user, text = input().split(':')
        messages.append(text)
        if user == '?':
            mu = mentioned_usernames(text)
            possible_users.append(usernames - mentioned_usernames(text))
        else:
            possible_users.append({user})

    # print(possible_users, file=sys.stderr)

    for i in range(m-1):
        if len(possible_users[i]) == 1:
            possible_users[i+1].difference_update(possible_users[i])
    for i in range(m-1, 0, -1):
        if len(possible_users[i]) == 1:
            possible_users[i-1].difference_update(possible_users[i])

    # print(possible_users, file=sys.stderr)

    res = []
    is_possible = True
    prev_user = '$'
    for i in range(m):
        if possible_users[i]:
            pusers = possible_users[i] - {prev_user}
            resx = next(iter(pusers))
            res.append(resx)
            prev_user = resx
        else:
            is_possible = False
            break

    if is_possible:
        for i in range(m):
            print('{}:{}'.format(res[i], messages[i]))
    else:
        print("Impossible")


3

# BEGIN template
import sys
import re
import pprint

def dbg(x,y=''):
  if len(y) > 0: y += ' = '
  sys.stderr.write('\n>>> '+y+pprint.pformat(x)+'\n')

oo = 0x3f3f3f3f3f3f3f3f
# END template

def main():
  t = int(input())
  for t in range(t):
    # input
    n = int(input())
    users = set(input().split())
    m = int(input())
    msg = []
    for i in range(m):
      user, text = input().split(':')
      alts = set()
      if user != '?':
        alts.add(user)
      else:
        # this shit is pretty fucked up, dude
        alts = users - {x for x in re.split(r'[^A-Za-z0-9]+',text)}
      msg.append(dict(user=user, text=text, users=alts))
    # remove before and after
    for i in range(m-1):
      if len(msg[i]['users']) == 1:
        msg[i+1]['users'].difference_update(msg[i]['users'])
    for i in range(m-1,0,-1):
      if len(msg[i]['users']) == 1:
        msg[i-1]['users'].difference_update(msg[i]['users'])
    # compute answer
    last = ''
    impo = False
    for i in range(m):
      msg[i]['users'].discard(last)
      if len(msg[i]['users']) == 0:
        impo = True
        break
      last = next(iter(msg[i]['users']))
      msg[i]['user'] = last
    if impo:
      print('Impossible')
      continue
    for i in range(m):
      print(msg[i]['user']+':'+msg[i]['text'])
    '''
    dp = [[0 for j in range(n+5)] for i in range(m+5)]
    for i in range(1,n+5):
      dp[m+1][i] = oo
    for i in range(m,0,-1):
      for j in range(n+1):
        for k in msg[i]['users']:
          if k != j and dp[i+1][k]:
            dp[i][j] = k
            break
    # output
    if not dp[1][0]:
      print('Impossible')
      continue
    j = 0
    for i in range(1,m+1):
      print(users[dp[i][j]]+':'+msg[i]['text'])
      j = dp[i][j]'''

main()


3

# BEGIN template
import sys
import re
import pprint

def dbg(x,y=''):
  if len(y) > 0: y += ' = '
  sys.stderr.write('\n>>> '+y+pprint.pformat(x)+'\n')

oo = 0x3f3f3f3f3f3f3f3f
# END template

def main():
  for t in range(int(input())):
    impo = False
    # input
    n = int(input())
    users = input().split()
    users_set = set(users)
    users.insert(0,'0')
    m = int(input())
    msg = [None]*(m+5)
    for i in range(1,m+1):
      user, text = input().split(':')
      alts = set()
      if user != '?': user = users.index(user)
      else:
        # this shit is pretty fucked up, dude
        for alt in users_set - {x for x in re.split(r'[^A-Za-z0-9]+',text)}:
          alts.add(users.index(alt))
      msg[i] = dict(user=user, text=text, users=alts)
    # remove before and after
    for i in range(1,m+1):
      if 1 <= i-1:  msg[i]['users'].discard(msg[i-1]['user'])
      if i+1 <= m:  msg[i]['users'].discard(msg[i+1]['user'])
      if msg[i]['user'] == '?' and len(msg[i]['users']) == 0:
        impo = True
        break
    if impo:
      print('Impossible')
      continue
    # compute answer
    dp = [[0 for j in range(n+5)] for i in range(m+5)]
    for i in range(n+5):
      dp[m+1][i] = oo
    for i in range(m,0,-1):
      u = msg[i]['user']
      for j in range(n+1):
        if u != '?':
          if u != j and dp[i+1][u]: dp[i][j] = u
        else:
          for alt in msg[i]['users']:
            if alt != j and dp[i+1][alt]:
              dp[i][j] = alt
              break
    # output
    if not dp[1][0]:
      print('Impossible')
      continue
    j = 0
    for i in range(1,m+1):
      print(users[dp[i][j]]+':'+msg[i]['text'])
      j = dp[i][j]

main()


3

# BEGIN template
import sys
import re
import pprint

def dbg(x,y=''):
  if len(y) > 0: y += ' = '
  sys.stderr.write('\n>>> '+y+pprint.pformat(x)+'\n')

oo = 0x3f3f3f3f3f3f3f3f
# END template

def main():
  for t in range(int(input())):
    # input
    n = int(input())
    users = input().split()
    users_set = set(users)
    users.insert(0,'0')
    m = int(input())
    msg = [None]*(m+5)
    for i in range(1,m+1):
      user, text = input().split(':')
      alts = set()
      if user != '?':
        user = users.index(user)
        alts.add(user)
      else:
        # this shit is pretty fucked up, dude
        for alt in users_set - {x for x in re.split('[^A-Za-z0-9]+',text)}:
          alts.add(users.index(alt))
      msg[i] = dict(user=user, text=text, users=alts)
    # remove before and after
    for i in range(1,m+1):
      if 1 <= i-1:  msg[i]['users'].discard(msg[i-1]['user'])
      if i+1 <= m:  msg[i]['users'].discard(msg[i+1]['user'])
    # compute answer
    dp = [[0 for j in range(n+5)] for i in range(m+5)]
    for i in range(n+5):
      dp[m+1][i] = oo
    for i in range(m,0,-1):
      for j in range(n+1):
        for k in msg[i]['users']:
          if k != j and dp[i+1][k]:
            dp[i][j] = k
            break
    # output
    if not dp[1][0]:
      print('Impossible')
      continue
    j = 0
    for i in range(1,m+1):
      print(users[dp[i][j]]+':'+msg[i]['text'])
      j = dp[i][j]

main()