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: HARD
Tags: Constructive algorithms

String algorithms

Implementation

Complete search

Dynamic programming
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
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
sys.exit(main())


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(' ')))
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


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


import re
t = int(input())
for z in range(t):
	n = int(input())
	users = input().split()
	m = int(input())
	can = [[] for i in range(m)]
	ok = True
	L = []
	for i in range(m):
		l = input().split(':')
		L += [l]
		if l[0] != '?':
			can[i] = [users.index(l[0])]
		else:
			can[i] = [x for x in range(n)]
		ll = re.sub('[^A-Za-z0-9]', ' ', l[1]).split()
		for j in ll:
			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='')


import re
global E
global W
counter = 0

def go(i):
	global 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(filter(lambda x: x in users_set, words))
		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')


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)
		elif 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()


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

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(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 sys
import re

def mentioned_usernames(line):
	return {x for x in re.split('[^A-Za-z0-9]+', line)}
t = int(input())
for ti in range(t):
	possible_users = []
	messages = []
	n = int(input())
	usernames = set(input().split())
	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})
	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
	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
import pprint

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

def main():
	for t in range(int(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:
				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)
		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'])
		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
		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()


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(filter(None, re.split('\\W+', msg)))
		dp.append((names if sender == '?' else set([sender])) - ls)
		if i and len(dp[i - 1]) == 1:
			dp[i] -= dp[i - 1]
	if any([len(p) == 0 for p in dp]):
		print('Impossible')
	else:
		res = []
		for i in reversed(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
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('[\\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])


3
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 = 4557430888798830399

def main():
	t = int(input())
	for t in range(t):
		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:
				alts = users - {x for x in re.split('[^A-Za-z0-9]+', text)}
			msg.append(dict(user=user, text=text, users=alts))
		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'])
		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'])
main()


import sys
trans = str.maketrans({c: ' ' for c in '.,?!'})

def check_chat(users, messages):
	m = len(messages)
	possible = [set(users) for i in range(m)]
	for (i, M) in enumerate(messages):
		if M[0] is None:
			possible[i] -= set(M[1].translate(trans).split())
		else:
			if i > 0:
				possible[i - 1].discard(M[0])
			if i < m - 1:
				possible[i + 1].discard(M[0])
	for (i, M) in enumerate(messages):
		if M[0] is not None:
			continue
		if i > 0 and messages[i - 1][0] is not None:
			possible[i].discard(messages[i - 1][0])
		if len(possible[i]) == 0:
			return None
		elif len(possible[i]) == 1:
			while i >= 0 and messages[i][0] is None:
				messages[i][0] = possible[i].pop()
				if i > 0:
					possible[i - 1].discard(messages[i][0])
				i -= 1
	for (i, M) in enumerate(messages):
		while i < m and messages[i][0] is None:
			messages[i][0] = possible[i].pop()
			if i < m - 1:
				possible[i + 1].discard(messages[i][0])
			i += 1
	return messages

def solve():
	t = int(input())
	for i in range(t):
		n = int(input())
		users = list(input().split())
		m = int(input())
		messages = []
		for i in range(m):
			message = input()
			k = message.index(':')
			name = message[:k]
			messages.append([name if name != '?' else None, message[k + 1:]])
		chat = check_chat(users, messages)
		if chat is None:
			print('Impossible')
		else:
			for message in messages:
				print('{0}:{1}'.format(message[0], message[1]))
solve()


import re

def proc(msgs):
	chg = False
	for (i, msg) in enumerate(msgs):
		if msg[0] != '?':
			continue
		ppn = msg[1]
		if i > 0:
			ppn.discard(msgs[i - 1][0])
		if i != len(msgs) - 1:
			ppn.discard(msgs[i + 1][0])
		if len(ppn) == 1:
			msg[0] = ppn.pop()
			chg = True
	return chg

def is_valid(msgs):
	for (i, msg) in enumerate(msgs):
		if msg[0] == '?' or (i > 0 and msg[0] == msgs[i - 1][0]) or (i != len(msgs) - 1 and msg[0] == msgs[i + 1][0]):
			return False
	return True
TC = int(input())
for tc in range(0, TC):
	N = int(input())
	persons = set(input().split())
	M = int(input())
	msgs = []
	for m in range(M):
		line = input()
		m1 = re.match('(.*)\\:(.*)', line)
		ppn = set(persons)
		for un in re.findall('[a-zA-Z0-9]+', m1.group(2)):
			ppn.discard(un)
		msgs.append([m1.group(1), ppn, m1.group(2)])
	while True:
		if proc(msgs):
			continue
		chgt = False
		for msg in msgs:
			if msg[0] == '?' and len(msg[1]) > 0:
				msg[0] = msg[1].pop()
				chgt = True
				break
		if not chgt:
			break
	if is_valid(msgs):
		for msg in msgs:
			print('%s:%s' % (msg[0], msg[2]))
	else:
		print('Impossible')


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}


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

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


import sys

def there_is(user, text):
	p = text.split(user)
	n = len(p)
	p[0] = ' ' if p[0] == '' else p[0]
	p[n - 1] = ' ' if p[n - 1] == '' else p[n - 1]
	for i in range(n - 1):
		if p[i] == '' or p[i + 1] == '':
			continue
		e = p[i][-1]
		b = p[i + 1][0]
		if e.isdigit() or e.isalpha() or b.isdigit() or b.isalpha():
			continue
		else:
			return True
	else:
		return False
number_test = int(input())
while number_test:
	n = int(input())
	user_list = list(input().rstrip().split())
	n = int(input())
	authors = []
	not_authors = []
	texts = []
	while n:
		input_data = input()
		(author, text) = input_data.split(':')
		authors.append(author)
		texts.append(text)
		not_authors.append([i for i in user_list if there_is(i, text)])
		n -= 1
	dp = []
	for i in range(len(authors)):
		dp.append({user: 0 for user in user_list})
	dp[0] = {user: 1 if (user == authors[0] or authors[0] == '?') and (not user in not_authors[0]) else 0 for user in user_list}
	for i in range(1, len(authors)):
		for prob_user in user_list if authors[i] == '?' else [authors[i]]:
			if prob_user in not_authors[i]:
				continue
			temp_list = [v for (k, v) in dp[i - 1].items() if k != prob_user]
			dp[i][prob_user] = max(temp_list, default=0) + 1
	if not len(authors) in dp[len(authors) - 1].values():
		print('Impossible')
	else:
		for i in range(len(authors) - 1, -1, -1):
			if authors[i] == '?':
				for user in user_list:
					if dp[i][user] == i + 1 and (i + 1 == len(authors) or authors[i + 1] != user) and (i - 1 == -1 or authors[i - 1] != user):
						authors[i] = user
						break
		for i in range(len(authors)):
			print(authors[i], ':', texts[i], sep='')
	number_test -= 1


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


from sys import stdin, stdout

def divide(s):
	strings = []
	l = 0
	r = len(s) - 1
	while l < len(s) and s[l] in '?!., ':
		l += 1
	while r >= 0 and s[r] in '?!., ':
		r -= 1
	s = s[l:r + 1]
	while len(s):
		for i in range(len(s)):
			if s[i] in '?!., ':
				if i:
					strings.append(s[:i])
				s = s[i + 1:]
				break
		else:
			strings.append(s)
			break
	return strings
nchats = int(stdin.readline())
for i in range(nchats):
	nnames = int(stdin.readline())
	names = list(stdin.readline().strip().split())
	nmessage = int(stdin.readline())
	useless = [[] for i in range(nmessage + 5)]
	text = []
	ans = []
	for j in range(nmessage):
		s = stdin.readline().strip()
		ans.append(s.split(':')[0])
		text.append(s.split(':')[1])
		string = divide(text[-1])
		for f in string:
			if f in names and f not in useless[j]:
				useless[j].append(f)
		if ans[j] != '?':
			if ans[j] not in useless[j - 1]:
				useless[j - 1].append(ans[j])
			if ans[j] not in useless[j + 1]:
				useless[j + 1].append(ans[j])
	label = 1
	while label:
		while label:
			label = 0
			for j in range(nmessage):
				if len(useless[j]) == nnames - 1 and ans[j] == '?':
					for f in names:
						if f not in useless[j]:
							ans[j] = f
							label = 1
							if ans[j] not in useless[j - 1]:
								useless[j - 1].append(ans[j])
							if ans[j] not in useless[j + 1]:
								useless[j + 1].append(ans[j])
							break
		for j in range(nmessage):
			if len(useless[j]) != nnames and ans[j] == '?':
				for f in names:
					if f not in useless[j]:
						ans[j] = f
						label = 1
						if ans[j] not in useless[j - 1]:
							useless[j - 1].append(ans[j])
						if ans[j] not in useless[j + 1]:
							useless[j + 1].append(ans[j])
						break
	if ans.count('?'):
		stdout.write('Impossible\n')
	else:
		for j in range(nmessage):
			stdout.write(ans[j] + ':' + text[j] + '\n')


import re, sys

def debug(*msg):
	print(*msg, file=sys.stderr)

def solve():

	def parse(line):
		mo = re.match('(.*?):(.*)', line)
		assert mo
		(name, text) = (mo[1], mo[2])
		if name == '?':
			speaker = -1
		else:
			assert name in revP
			speaker = revP[name]
		appears = [False] * n
		for x in re.findall('\\w+', text):
			if x in revP:
				appears[revP[x]] = True
		return (speaker, text, appears)

	def add_hist(j):
		for hist in prev:
			if hist and hist[len(hist) - 1] == j:
				continue
			cur.append(hist + [j])
			return
	n = int(input())
	P = input().strip().split()
	revP = {P[i]: i for i in range(n)}
	m = int(input())
	lines = []
	for i in range(m):
		lines.append(sys.stdin.readline().strip())
	cur = [[]]
	texts = []
	for i in range(m):
		prev = cur
		cur = []
		(speaker, text, appears) = parse(lines[i])
		texts.append(text)
		if speaker >= 0:
			add_hist(speaker)
		else:
			for j in range(n):
				if not appears[j]:
					add_hist(j)
		if not cur:
			print('Impossible')
			return
	debug('cur=', cur, 'texts=', texts, 'revP=', revP)
	for i in range(m):
		print(f'{P[cur[0][i]]}:{texts[i]}')

def main():
	t = int(input())
	for tt in range(t):
		solve()
main()


def solve():
	global msg, rem, m
	flag = True
	while flag:
		flag = False
		for i in range(m):
			if msg[i][0] == ' ':
				if len(rem[i]) == 0:
					return False
				elif len(rem[i]) == 1:
					flag = True
					msg[i][0] = rem[i][0]
					if i > 0:
						try:
							rem[i - 1].remove(rem[i][0])
						except ValueError:
							pass
					if i < m - 1:
						try:
							rem[i + 1].remove(rem[i][0])
						except ValueError:
							pass
	for i in range(m):
		if len(rem[i]) >= 1:
			msg[i][0] = rem[i][0]
			if i > 0:
				try:
					rem[i - 1].remove(rem[i][0])
				except ValueError:
					pass
			if i < m - 1:
				try:
					rem[i + 1].remove(rem[i][0])
				except ValueError:
					pass
	return True
t = int(input())
for _ in range(t):
	global msg, rem, m
	n = int(input())
	names = input().split()
	m = int(input())
	msg = list()
	sm = list()
	for i in range(m):
		sm.append(input())
		msg.append(sm[-1].replace('.', ' ').replace(',', ' ').replace('!', ' ').replace('?', ' ').split(':'))
		msg[-1][1] = msg[-1][1].split()
	for (i, data) in enumerate(msg):
		if data[0] != ' ':
			if i > 0:
				msg[i - 1][1].append(data[0])
			if i < m - 1:
				msg[i + 1][1].append(data[0])
	rem = [[s for s in names if not s in msg[i][1]] if msg[i][0] == ' ' else [] for i in range(m)]
	if solve():
		for i in range(m):
			if sm[i][0] == '?':
				print(msg[i][0] + sm[i][1:])
			else:
				print(sm[i])
	else:
		print('Impossible')


from sys import *
t = int(stdin.readline())
for sssss in range(t):
	(text, ps, dn, n, names, m) = ([], [], dict(), int(stdin.readline()), stdin.readline().split(), int(stdin.readline()))
	for i in range(len(names)):
		dn[names[i]] = i
	for i in range(m):
		nxt = stdin.readline()
		getname = nxt.split(':')[0]
		nxt = nxt.split(':')[1]
		text.append(nxt)
		if getname == '?':
			(pos, hell, shit) = (set([z for z in range(n)]), '', set(['.', ',', '!', '?']))
			for y in nxt:
				if y in shit:
					hell += ' '
				else:
					hell += y
			nhere = hell.split()
			for j in nhere:
				pos.discard(dn.get(j))
			if i and len(ps[-1]) == 1:
				for dd in ps[-1]:
					pos.discard(dd)
			ps.append(pos)
		else:
			if i:
				ps[-1].discard(dn[getname])
			ps.append(set([dn[getname]]))
	(dp, yy, ban) = ([[False] * n], [0] * m, -1)
	for i in ps[0]:
		dp[0][i] = True
	for i in range(1, m):
		dp.append([False] * n)
		for j in ps[i]:
			for k in range(n):
				if k != j and dp[-2][k] == True:
					dp[-1][j] = True
					break
	if True not in dp[-1]:
		stdout.write('Impossible\n')
		continue
	for i in range(m - 1, -1, -1):
		for j in range(n):
			if j != ban and dp[i][j]:
				ban = j
				yy[i] = j
				break
	for i in range(m):
		stdout.write(names[yy[i]] + ':' + text[i])