Given a list of contacts contact[] of length n where each contact is a string which exist in a phone directory and a query string s. The task is to implement a search query for the phone directory. Run a search query for each prefix p of the query string s (i.e. from  index 1 to |s|) that prints all the distinct contacts which have the same prefix as p in lexicographical increasing order. Please refer the explanation part for better understanding.
Note: If there is no match between query and contacts, print "0".
Example 1:
Input: 
n = 3
contact[] = {"geeikistest", "geeksforgeeks", 
"geeksfortest"}
s = "geeips"
Output:
geeikistest geeksforgeeks geeksfortest
geeikistest geeksforgeeks geeksfortest
geeikistest geeksforgeeks geeksfortest
geeikistest
0
0
Explaination: By running the search query on 
contact list for "g" we get: "geeikistest", 
"geeksforgeeks" and "geeksfortest".
By running the search query on contact list 
for "ge" we get: "geeikistest" "geeksforgeeks"
and "geeksfortest".
By running the search query on contact list 
for "gee" we get: "geeikistest" "geeksforgeeks"
and "geeksfortest".
By running the search query on contact list 
for "geei" we get: "geeikistest".
No results found for "geeip", so print "0". 
No results found for "geeips", so print "0".
Your Task:
You do not need to read input or print anything. Your task is to complete the function displayContacts() which takes n, contact[ ] and s as input parameters and returns a list of list of strings for required prefixes. If some prefix has no matching contact return "0" on that list.
Expected Time Complexity: O(|s| * n * max|contact[i]|)
Expected Auxiliary Space: O(n * max|contact[i]|)
Constraints:
1 ≤ T ≤ 100, T = number of test cases
1 ≤ n ≤ 50
1 ≤ |contact[i]| ≤ 50
1 ≤ |s| ≤ 6

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|s| * n * max|contact[i]|)
Expected Auxiliary Space: O(n * max|contact[i]|)

Starter code:
#User function Template for python3



class Solution:

    def displayContacts(self, n, contact, s):

        # code here

Solutions:
import re

class Solution:

	def displayContacts(self, n, contact, s):
		hoi = sorted(contact)
		jo = ' '.join(hoi)
		lst = []
		x = ''
		for i in s:
			x += i
			d = []
			orderRegex = re.compile('(\\b{})'.format(x))
			mo = orderRegex.findall('{}'.format(jo))
			if mo:
				for j in hoi:
					if re.search('\\b{}'.format(mo[0]), j):
						d.append(j)
					if len(d) >= 2 and d[-1] == d[-2]:
						d.remove(d[-1])
				lst.append(d)
			else:
				lst.append([0])
		return lst


class Solution:

	class Node:

		def __init__(self, ch):
			self.data = ch
			self.children = [None] * 26
			self.isTerminal = False

	class Trie:

		def __init__(self):
			self.root = Solution.Node('\x00')

		def insert(self, root, key):
			if len(key) == 0:
				root.isTerminal = True
				return
			index = ord(key[0]) - ord('a')
			child = None
			if root.children[index] is not None:
				child = root.children[index]
			else:
				child = Solution.Node(key[0])
				root.children[index] = child
			self.insert(child, key[1:])

		def insertWord(self, word):
			self.insert(self.root, word)

		def printSuggestions(self, curr, temp, prefix):
			if curr.isTerminal:
				temp.append(prefix)
			for ch in range(ord('a'), ord('z') + 1):
				next_node = curr.children[ch - ord('a')]
				if next_node is not None:
					prefix += chr(ch)
					self.printSuggestions(next_node, temp, prefix)
					prefix = prefix[:-1]

		def getSuggestions(self, s):
			prev = self.root
			output = []
			prefix = ''
			i = 0
			for i in range(len(s)):
				lastch = s[i]
				prefix += lastch
				curr = prev.children[ord(lastch) - ord('a')]
				if curr is None:
					break
				temp = []
				self.printSuggestions(curr, temp, prefix)
				output.append(temp)
				prev = curr
			if i < len(s):
				while i < len(s):
					output.append(['0'])
					i += 1
			return output

	def displayContacts(self, n, contact, s):
		t = Solution.Trie()
		for i in range(n):
			str = contact[i]
			t.insertWord(str)
		return t.getSuggestions(s)


class Node:

	def __init__(self, ch='/0'):
		self.ch = ch
		self.childrens = [None] * 26
		self.is_end_of_word = False

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, word):
		root = self.root
		for ch in word:
			idx = ord(ch) - ord('a')
			if root.childrens[idx] is None:
				root.childrens[idx] = Node(ch)
			root = root.childrens[idx]
		root.is_end_of_word = True

class Solution:

	def get_words(self, root, word, ans):
		if root.is_end_of_word:
			ans.append(word)
		for child in root.childrens:
			if child:
				word += child.ch
				self.get_words(child, word, ans)
				word = word[:-1]

	def displayContacts(self, n, contact, s):
		t = Trie()
		for name in contact:
			t.insert(name)
		res = [[0]] * len(s)
		word = ''
		root = t.root
		for i in range(len(s)):
			is_word_exist = False
			for child in root.childrens:
				if child and child.ch == s[i]:
					is_word_exist = True
					root = child
					ans = []
					self.get_words(root, s[:i + 1], ans)
					res[i] = ans
					break
			if not is_word_exist:
				break
		return res


class trieNode:

	def __init__(self):
		self.child = [None] * 26
		self.isLast = False

class Trie:

	def __init__(self):
		self.root = trieNode()

	def insert(self, a):
		curr = self.root
		for el in a:
			if curr.child[ord(el) - ord('a')] == None:
				curr.child[ord(el) - ord('a')] = trieNode()
			curr = curr.child[ord(el) - ord('a')]
		curr.isLast = True

	def insertIntoTrie(self, contact, n):
		for i in range(n):
			self.insert(contact[i])

class Solution:

	def displayContactsUtil(self, curNode, prefix, vec):
		if curNode.isLast:
			vec.append(prefix)
		for c in range(26):
			i = chr(ord('a') + c)
			nextNode = curNode.child[c]
			if nextNode != None:
				self.displayContactsUtil(nextNode, prefix + i, vec)

	def displayContacts(self, n, contact, s):
		trie = Trie()
		trie.insertIntoTrie(contact, n)
		prevnode = trie.root
		res = []
		prefix = ''
		_len = len(s)
		i = 0
		while i < _len:
			v = []
			prefix += s[i]
			last_char = prefix[i]
			curNode = prevnode.child[ord(last_char) - ord('a')]
			if curNode is None:
				v.append('0')
				res.append('0')
				i += 1
				break
			else:
				self.displayContactsUtil(curNode, prefix, v)
				prevnode = curNode
				res.append(v[:])
				i += 1
		while i < _len:
			res.append(['0'])
			i += 1
		return res


class Solution:

	def displayContacts(self, n, arr, qList):
		dct = dict()
		for i in arr:
			for j in range(len(i)):
				if i[:j + 1] in dct:
					dct[i[:j + 1]].add(i)
				else:
					dct[i[:j + 1]] = set()
					dct[i[:j + 1]].add(i)
		ans = []
		for i in range(len(qList)):
			if qList[:i + 1] in dct:
				ans.append(sorted(list(dct[qList[:i + 1]])))
			else:
				ans.append([0])
		return ans


class Solution:

	def displayContacts(self, n, contact, s):
		str = ''
		ans = []
		for i in s:
			str += i
			temp = []
			for j in contact:
				if str in j and j not in temp:
					temp.append(j)
			if len(temp) == 0:
				ans.append(['0'])
			else:
				ans.append(sorted(temp))
		return ans


class Solution:

	def displayContacts(self, n, contact, s):
		contact = list(set(contact))
		contact.sort()
		l = []
		for i in range(1, len(s) + 1):
			S = s[:i]
			l1 = []
			flag = 0
			for j in contact:
				if j[:i] == S:
					l1.append(j)
					flag = 1
			if flag == 1:
				l.append(l1)
			else:
				l.append('0')
		return l


class TrieNode:

	def __init__(self):
		self.children = {}
		self.isEnd = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word):
		cur = self.root
		for c in word:
			if c not in cur.children:
				cur.children[c] = TrieNode()
			cur = cur.children[c]
		cur.isEnd = True

	def search(self, prefix, res, curNode):
		if curNode.isEnd:
			res.append(prefix)
		for c in 'abcdefghijklmnopqrstuvwxyz':
			if c in curNode.children:
				nextNode = curNode.children[c]
				if nextNode:
					self.search(prefix + c, res, nextNode)

class Solution:

	def displayContacts(self, n, contact, s):
		t = Trie()
		for w in contact:
			t.insert(w)
		res = []
		prevNode = t.root
		prefix = ''
		for (i, c) in enumerate(s):
			prefix = prefix + c
			temp = []
			cur = prevNode.children.get(c)
			if not cur:
				break
			t.search(prefix, temp, cur)
			res.append(temp)
			prevNode = cur
		for j in range(i, len(s)):
			res.append(['0'])
		return res


import string

class Node:

	def __init__(self, ch):
		self.data = ch
		self.childrens = [None] * 26
		self.is_terminal = False

	def __str__(self) -> str:
		return self.data

class Trie:

	def __init__(self):
		self.root = Node('\x00')

	def insert(self, root, word):
		for ch in word:
			idx = ord(ch) - ord('a')
			if root.childrens[idx] is None:
				root.childrens[idx] = Node(ch)
			root = root.childrens[idx]
		root.is_terminal = True

class Solution:

	def get_all_words(self, root, temp, prefix):
		if root.is_terminal:
			temp.append(prefix)
		for node in root.childrens:
			if node:
				prefix += node.data
				self.get_all_words(node, temp, prefix)
				prefix = prefix[:-1]

	def get_suggestions(self, curr, s):
		prev = curr
		outputs = []
		prefix = ''
		for ch in s:
			prefix += ch
			idx = ord(ch) - ord('a')
			curr = prev.childrens[idx]
			if curr is None:
				break
			temp = []
			self.get_all_words(curr, temp, prefix)
			outputs.append(temp)
			prev = curr
		return outputs

	def displayContacts(self, n, contact, s):
		t = Trie()
		for c in contact:
			t.insert(t.root, c)
		outputs = self.get_suggestions(t.root, s)
		for i in range(len(s) - len(outputs)):
			outputs.append(['0'])
		return outputs


class Solution:

	def displayContacts(self, n, contact, s):
		t = []
		for i in range(1, len(s) + 1):
			c = []
			for j in sorted(set(contact)):
				if j.startswith(s[:i]):
					c.append(j)
			if c == []:
				t.append([0])
			else:
				t.append(c)
		return t


class Solution:

	def displayContacts(self, n, contact, s):
		match_s = ''
		ans = []
		for i in range(len(s)):
			match_s += s[i]
			temp = []
			se = set()
			for j in range(n):
				to_match = contact[j][:i + 1]
				if match_s == to_match:
					if contact[j] not in se:
						temp.append(contact[j])
						se.add(contact[j])
			if len(temp) != 0:
				temp.sort()
				ans.append(temp)
			else:
				ans.append([0])
		return ans


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.matchedWords = set()

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def addWord(self, word):
		root = self.root
		for x in word:
			idx = ord(x) - ord('a')
			if root.children[idx] == None:
				root.children[idx] = TrieNode()
			root = root.children[idx]
			root.matchedWords.add(word)

	def searchWord(self, word):
		root = self.root
		searchResult = []
		for x in word:
			idx = ord(x) - ord('a')
			if not root or root.children[idx] == None:
				searchResult.append([0])
				root = None
			else:
				root = root.children[idx]
				searchResult.append(sorted(list(root.matchedWords)))
		return searchResult

class Solution:

	def displayContacts(self, n, contact, s):
		trie = Trie()
		for person in contact:
			trie.addWord(person)
		return trie.searchWord(s)


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Solution:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word):
		curr = self.root
		for i in word:
			idx = ord(i) - ord('a')
			if curr.children[idx] is None:
				curr.children[idx] = TrieNode()
			curr = curr.children[idx]
		curr.isEndOfWord = True

	def getResponseUtil(self, curr, prefix, ans):
		if curr.isEndOfWord:
			ans.append(prefix)
		for i in range(26):
			new = curr.children[i]
			if new:
				self.getResponseUtil(new, prefix + chr(ord('a') + i), ans)
		return ans

	def getResponse(self, s):
		prev = self.root
		prefix = ''
		res = []
		l = len(s)
		for i in range(l):
			prefix += s[i]
			lastchar = prefix[i]
			curr = prev.children[ord(lastchar) - ord('a')]
			if not curr:
				break
			res.append(self.getResponseUtil(curr, prefix, []))
			prev = curr
		return res

	def displayContacts(self, n, contact, s):
		for i in contact:
			self.insert(i)
		res = self.getResponse(s)
		l = len(res)
		for i in range(len(s) - l):
			res.append([0])
		return res


from collections import defaultdict

class Solution:

	def displayContacts(self, n, contact, s):
		if not s or not contact:
			return []
		mp = defaultdict(int)
		for i in range(n):
			mp[contact[i]] += 1
		ans = []
		for i in range(len(s)):
			v = []
			for k in sorted(mp.keys()):
				if k[:i + 1] == s[:i + 1]:
					v.append(k)
			if len(v) == 0:
				v.append(0)
			ans.append(v)
		return ans


from collections import defaultdict

class node:

	def __init__(self):
		self.parent = defaultdict(None)
		self.flag = set()

class trie:

	def __init__(self):
		self.root = node()

	def addWord(self, word, index):
		temp = self.root
		for i in range(len(word)):
			if word[i] not in temp.parent:
				temp.parent[word[i]] = node()
			temp = temp.parent[word[i]]
			temp.flag.add(index)

	def searchPrefix(self, pref):
		temp = self.root
		for i in range(len(pref)):
			if pref[i] not in temp.parent:
				return set()
			temp = temp.parent[pref[i]]
		return temp.flag

class Solution:

	def displayContacts(self, n, contact, s):
		ans = []
		t = trie()
		for (i, ele) in enumerate(contact):
			t.addWord(ele, i)
		for i in range(len(s)):
			k = t.searchPrefix(s[:i + 1])
			ls = list(set((contact[ele] for ele in k)))
			if len(ls) == 0:
				ans.append([0])
			else:
				ls.sort()
				ans.append(ls)
		return ans


class TrieNode:

	def __init__(self, char):
		self.char = char
		self.children = {}
		self.word_end = False

class Trie:

	def __init__(self):
		self.root = TrieNode('')

	def insert(self, word: str) -> None:
		temp = self.root
		for char in word:
			if char in temp.children:
				temp = temp.children[char]
			else:
				new_node = TrieNode(char)
				temp.children[char] = new_node
				temp = new_node
		temp.word_end = True

	def search(self, word: str) -> bool:
		temp = self.root
		for char in word:
			if char in temp.children:
				temp = temp.children[char]
			else:
				return False
		if temp.word_end:
			return True
		else:
			return False

	def dfs(self, node: TrieNode, prefix: str) -> None:
		if node.word_end:
			self.output.append(prefix + node.char)
		for child in node.children.values():
			self.dfs(child, prefix + node.char)

	def startsWith(self, prefix: str):
		temp = self.root
		self.output = []
		for char in prefix:
			if char in temp.children:
				temp = temp.children[char]
			else:
				return []
		self.dfs(temp, prefix[:-1])
		return sorted(self.output)

class Solution:

	def displayContacts(self, n, contact, s):
		trie = Trie()
		for entry in contact:
			trie.insert(entry)
		ans = []
		query = ''
		for i in range(len(s)):
			query += s[i]
			this_ans = trie.startsWith(query)
			if len(this_ans) == 0:
				ans.append([0])
			else:
				ans.append(this_ans)
		return ans


class Node:

	def __init__(self):
		self.d = {}
		self.isEnd = False
		self.isPrefix = False

class Solution:

	def displayContacts(self, n, contact, s):
		root = Node()
		contact = list(set(contact))
		contact.sort()
		curr = root
		for letter in s:
			if letter not in curr.d:
				curr.d[letter] = Node()
			curr = curr.d[letter]
			curr.isPrefix = True
		curr.isEnd = True
		curr.isPrefix = True
		ans = [[]] * len(s)
		for word in contact:
			curr = root
			count = 0
			for letter in word:
				if letter not in curr.d:
					curr.d[letter] = Node()
				curr = curr.d[letter]
				if curr.isPrefix:
					if ans[count]:
						ans[count].append(word)
					else:
						ans[count] = [word]
					count += 1
			curr.isEnd = True
		for l in ans:
			if not l:
				l.append(0)
		return ans


class Solution:

	def displayContacts(self, n, contact, s):
		tempStr = ''
		answer = []
		for ch in s:
			tempStr += ch
			contact_list = []
			for con in contact:
				if tempStr in con and con not in contact_list:
					contact_list.append(con)
			if contact_list == []:
				answer.append(['0'])
			else:
				answer.append(sorted(contact_list))
		return answer


class Solution:

	def displayContacts(self, n, contact, s):
		s2 = []
		for i in range(0, len(s)):
			count = 0
			s3 = []
			for s1 in contact:
				if s1.startswith(s[0:i + 1]):
					s3.append(s1)
					count += 1
			if count == 0:
				s3.append(0)
			s3 = set(s3)
			s3 = list(s3)
			s3.sort()
			s2.append(s3)
		return s2


import re

class Solution:

	def displayContacts(self, n, contact, s):
		contact = list(set(contact))
		contact.sort()
		m = len(s)
		ans = [[]] * m
		str = ''
		for i in range(m):
			str += s[i]
			for name in contact:
				res = re.match(str, name, re.IGNORECASE)
				if res:
					if ans[i]:
						ans[i].append(name)
					else:
						ans[i] = [name]
		for l in ans:
			if not l:
				l.append(0)
		return ans


class Solution:

	def displayContacts(self, n, contact, s):
		con = []
		for x in range(1, len(s) + 1):
			if not contact:
				con.append([0])
				continue
			contact = sorted(set([_ for _ in contact if _.find(s[:x]) == 0]))
			if not contact:
				con.append([0])
			else:
				con.append(contact)
		return con


from collections import defaultdict

class Solution:

	def displayContacts(self, n, contact, s):
		m = defaultdict(set)
		contact.sort()
		for i in contact:
			for j in range(1, len(i) + 1):
				m[i[:j]].add(i)
		res = []
		for i in range(1, len(s) + 1):
			if s[:i] in m:
				res.append(sorted(m[s[:i]]))
			else:
				res.append([0])
		return res


class Solution:

	def displayContacts(self, n, contact, s):

		def check(ind, letter, word):
			return ind < len(word) and word[ind] == letter
		contact = sorted(set(contact))
		res = []
		temp = []
		for (ind, letter) in enumerate(s):
			temp = []
			for word in contact:
				if check(ind, letter, word):
					temp.append(word)
			if not temp:
				res.append([0])
			else:
				res.append(temp)
			contact[:] = temp
		return res


class Solution:

	def displayContacts(self, n, contacts, s):
		contacts = list(set(contacts))
		contacts.sort()
		d = {x: True for x in contacts}
		ans = []
		for i in range(len(s)):
			curr = []
			for con in contacts:
				if d[con]:
					if len(con) > i and s[i] == con[i]:
						curr.append(con)
					else:
						d[con] = False
			if len(curr) > 0:
				ans.append(curr)
			else:
				ans.append([0])
		return ans


class TrieNode:

	def __init__(self):
		self.isEndOfWord = False
		self.children = [None] * 26

class Solution:

	def __init__(self):
		self.root = TrieNode()

	def displayContacts(self, n, contact, s):
		ans = []
		for each in contact:
			self.insertTrie(self.root, each)
		if not s or len(s) == 0:
			return []
		search_str = ''
		node = self.root
		for i in range(len(s)):
			search_str += s[i]
			index = ord(s[i]) - ord('a')
			res = []
			if node:
				node = node.children[index]
			if node is None:
				res.append('0')
			else:
				self.dfs(node, res, search_str)
			ans.append(res)
		return ans

	def dfs(self, node, res, search_str):
		if node.isEndOfWord:
			res.append(search_str)
		for i in range(26):
			if node.children[i]:
				char = chr(ord('a') + i)
				self.dfs(node.children[i], res, search_str + char)

	def insertTrie(self, root, key):
		if len(key) == 0:
			root.isEndOfWord = True
			return
		node = TrieNode()
		index = ord(key[0]) - ord('a')
		if root.children[index]:
			node = root.children[index]
		else:
			root.children[index] = node
		self.insertTrie(node, key[1:])


def helper(s, w):
	n = min(len(w), len(s))
	total = 0
	for i in range(n):
		if w[i] == s[i]:
			total += 1
		else:
			break
	return total

def function(con, s):
	stack = []
	maxi = 0
	con = sorted(list(set(con)))
	for word in con:
		total = helper(s, word)
		stack.append([word, total])
		maxi = max(maxi, total)
	result = []
	while maxi > 0:
		temp = []
		for st in stack:
			if st[-1] > 0:
				temp.append(st[0])
			st[-1] -= 1
		maxi -= 1
		result.append(temp)
	result.extend(['0'] * (len(s) - len(result)))
	return result

class Solution:

	def displayContacts(self, n, contact, s):
		contact = sorted(contact)
		return function(contact, s)


class Node:

	def __init__(self):
		self.children = {}
		self.finish = False

class Trie:

	def __init__(self):
		self.root = Node()

	def addData(self, root, data):
		for i in data:
			if i not in root.children:
				root.children[i] = Node()
			root = root.children[i]
		root.finish = True

class Solution:

	def getAllMatchingStrings(self, root, temp, result):
		if root.finish == True:
			temp_ = ''.join(temp)
			result.append(temp_)
		if root.finish == True and len(root.children) != 0:
			for i in sorted(root.children):
				temp.append(i)
				self.getAllMatchingStrings(root.children[i], temp, result)
				temp.pop()
		else:
			for i in sorted(root.children):
				temp.append(i)
				self.getAllMatchingStrings(root.children[i], temp, result)
				temp.pop()

	def displayContacts(self, n, contact, s):
		t = Trie()
		for i in contact:
			t.addData(t.root, i)
		tempString = ''
		mainResult = []
		for i in s:
			tempString += i
			temp = []
			result = []
			tempRoot = t.root
			for i in tempString:
				if i in tempRoot.children:
					tempRoot = tempRoot.children[i]
				else:
					mainResult.append([0])
					break
			else:
				newResult = []
				self.getAllMatchingStrings(tempRoot, temp, result)
				for i in result:
					tempResult = tempString + i
					newResult.append(tempResult)
				mainResult.append(newResult)
		return mainResult


class TrieNode:

	def __init__(self):
		(self.children, self.is_word_end) = ({}, False)

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word):
		ptr = self.root
		for ch in word:
			if ch not in ptr.children:
				ptr.children[ch] = TrieNode()
			ptr = ptr.children[ch]
		ptr.is_word_end = True

	def find_next_char_node(self, ptr, ch):
		if ch not in ptr.children:
			return None
		return ptr.children[ch]

class Solution:

	def __dfs_over_trie(self, ptr, tmp_str, tmp_lst):
		if ptr.is_word_end:
			tmp_lst.append(''.join(tmp_str))
		if not ptr.children:
			return
		for (ch, node) in ptr.children.items():
			tmp_str.append(ch)
			self.__dfs_over_trie(node, tmp_str, tmp_lst)
			tmp_str.pop()

	def displayContacts(self, n, contact, s):
		tri = Trie()
		for word in contact:
			tri.insert(word)
		res = [[0] for ch in s]
		(tmp_str, ptr, count) = ([], tri.root, 0)
		for ch in s:
			ptr = tri.find_next_char_node(ptr, ch)
			if ptr == None:
				break
			tmp_lst = []
			tmp_str.append(ch)
			self.__dfs_over_trie(ptr, tmp_str, tmp_lst)
			tmp_lst.sort()
			res[count] = tmp_lst
			count += 1
		return res


class Solution:

	def displayContacts(self, n, contact, s):
		output = []
		remainingContact = contact
		remainingContact = list(dict.fromkeys(remainingContact))
		remainingContact.sort()
		for i in range(1, len(s) + 1):
			addOutput = []
			for testContact in remainingContact:
				if testContact[:i] == s[:i]:
					addOutput.append(testContact)
			if addOutput != []:
				output.append(addOutput)
				remainingContact = addOutput
			else:
				output.append([0])
		return output


class Solution:

	def displayContacts(self, n, contact, s):
		contact = sorted(list(set(contact)))
		ans = []
		for i in range(len(s)):
			temp = []
			for j in contact:
				if s[:i + 1] == j[:i + 1]:
					temp.append(j)
			if len(temp) > 0:
				ans.append(temp)
			else:
				ans.append([0])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		contact = input().split()
		s = input()
		ob = Solution()
		ans = ob.displayContacts(n, contact, s)
		for i in range(len(s)):
			for val in ans[i]:
				print(val, end=' ')
			print()


class Solution:

	def displayContacts(self, n, contact, s):
		contact = sorted(list(set(contact)))
		res = []
		for i in range(len(s)):
			temp = []
			for j in contact:
				if s[:i + 1] == j[:i + 1]:
					temp.append(j)
			if temp:
				res.append(temp)
			else:
				res.append([0])
		return res


class Solution:

	def displayContacts(self, n, contact, s):
		ans = []
		for i in range(1, len(s) + 1):
			prefix = s[:i]
			string = []
			for x in contact:
				if x[:i] == prefix:
					string.append(x)
			if len(string) == 0:
				ans.append([0])
			else:
				string = list(set(string))
				string.sort()
				ans.append(string)
		return ans


class Node:

	def __init__(self):
		self.sign = 0
		self.dct = {}

class Solution:

	def displayContacts(self, n, contact, s):
		ans = []
		contact = [num for num in set(contact)]
		contact.sort()
		root = Node()
		for num in contact:
			temp = root
			for key in num:
				temp.dct.setdefault(key, [Node()]).append(num)
				temp = temp.dct[key][0]
			temp.sign = 1
		temp = root
		for key in s:
			if key not in temp.dct:
				break
			ans.append(temp.dct[key][1:])
			temp = temp.dct[key][0]
		count = len(s) - len(ans)
		for _ in range(count):
			ans.append([0])
		return ans


class Node:

	def __init__():
		self.sign = 0
		self.dct = {}

class Solution:

	def displayContacts(self, n, contact, s):
		ans = []
		contact = [num for num in set(contact)]
		contact.sort()
		for i in range(len(s)):
			temp = []
			for nu in contact:
				try:
					if nu[i] == s[i]:
						temp.append(nu)
				except IndexError:
					pass
			if temp:
				ans.append(temp)
			else:
				ans.append([0])
			contact = temp.copy()
			temp = []
		return ans


class Solution:

	def displayContacts(self, n, contact, s):
		import collections
		m = collections.defaultdict(set)
		contact.sort()
		for i in contact:
			for j in range(len(i)):
				m[i[:j + 1]].add(i)
		res = [0] * len(s)
		for i in range(len(s)):
			res[i] = sorted(m.get(s[:i + 1], [0]))
		return res


class Solution:

	def displayContacts(self, n, contact, s):
		ans = []
		d = dict()
		for i in range(1, len(s) + 1):
			l = []
			for c in contact:
				d[c] = 0
			for c in contact:
				if c[0:i] == s[0:i]:
					if d[c] == 0:
						l.append(c)
						d[c] = 1
			if len(l) == 0:
				l.append(0)
			l.sort()
			ans.append(l)
		return ans


class Solution:

	def displayContacts(self, n, contacts, s):
		solution_string_array = []
		hit_zero = False
		contacts.sort()
		for i in range(len(s)):
			prefix = s[:i + 1]
			hits = []
			last_contact = ''
			if not hit_zero:
				for contact in contacts:
					if contact != last_contact:
						contact_prefix = contact[:i + 1]
						if contact_prefix == prefix:
							hits.append(contact)
							last_contact = contact
			if len(hits) > 0:
				solution_string_array.append(hits)
			else:
				hit_zero = True
				solution_string_array.append(['0'])
			contacts = hits
		return solution_string_array


class Solution:

	def displayContacts(self, n, contacts, s):
		res = []
		c = set(contacts)
		contacts = list(c)
		contacts.sort()
		for (idx, c) in enumerate(s):
			res.append([])
			str = s[:idx + 1]
			cnt = 0
			for contact in contacts:
				if contact[:len(str)] == str:
					res[idx].append(contact)
					cnt += 1
			if cnt == 0:
				res[idx].append(0)
		return res


class Solution:

	def printContacts(self, contact, s):
		out = []
		for p in contact:
			if p.startswith(s):
				out.append(p)
		if len(out) > 0:
			out = list(set(out))
			out.sort()
			return out
		else:
			return ['0']

	def displayContacts(self, n, contact, s):
		out = []
		for l in range(len(s)):
			out.append(self.printContacts(contact, s[:l + 1]))
		return out


class Solution:

	def displayContacts(self, n, contact, s):
		i = 0
		arr = []
		while i <= len(s):
			i += 1
			arr1 = {}
			for c in contact:
				if s[:i] == c[:i]:
					arr1[c] = 1
			arr2 = list(arr1.keys())
			arr2.sort()
			if len(arr2):
				arr.append(arr2)
			else:
				arr.append(['0'])
		return arr


class Solution:

	def displayContacts(self, n, contact, s):
		res = []
		i = 0
		while i <= len(s):
			i += 1
			j = {}
			for l in contact:
				if l.startswith(s[:i]):
					j[l] = l
			if len(j.keys()) == 0:
				res.append(['0'])
			else:
				asa = list(j.keys())
				asa.sort()
				res.append(asa)
		return res


import collections

class Solution:

	def displayContacts(self, n, contact, s):

		def addWord(word):
			current = root
			for char in word:
				current = current.addChild(char)
			current.isWord = True

		def findWords(prefix, node):
			stack = [(prefix, node)]
			words = []
			while stack:
				(currentPrefix, node) = stack.pop()
				newPrefix = currentPrefix + [node.char]
				if node.isWord:
					words.append(''.join(newPrefix))
				for child in node.child:
					if child:
						stack.append((newPrefix, child))
			return sorted(words)
		root = TrieNode('-1')
		for name in contact:
			addWord(name)
		output = [[0]] * len(s)
		current = root
		prefix = []
		for i in range(len(s)):
			char = s[i]
			current = current.child[current.getChildIdx(char)]
			if not current:
				break
			output[i] = findWords(prefix, current)
			prefix.append(char)
		return output

class TrieNode:

	def __init__(self, char):
		self.char = char
		self.child = [None] * 26
		self.isWord = False

	def addChild(self, char):
		childIdx = self.getChildIdx(char)
		if self.child[childIdx] == None:
			self.child[childIdx] = TrieNode(char)
		return self.child[childIdx]

	def getChildIdx(self, char):
		return ord('a') - ord(char)


from collections import defaultdict

class Solution:

	def displayContacts(self, n, contact, s):
		d = defaultdict(set)
		for word in contact:
			for i in range(1, len(word) + 1):
				d[word[:i]].add(word)
		ans = []
		for i in range(1, len(s) + 1):
			if s[:i] in d:
				ans.append(sorted(list(d[s[:i]])))
			else:
				ans.append('0')
		return ans


class Solution:

	def displayContacts(self, n, contact, s):
		res = []
		ans = []
		for _ in range(len(s)):
			res.append(set())
		query = ''
		for i in range(len(s)):
			query += s[i]
			for j in range(n):
				if query == contact[j][0:i + 1]:
					res[i].add(contact[j])
				elif j == n - 1 and len(res[i]) == 0:
					res[i].add(0)
		for li in res:
			ans.append(sorted(list(li)))
		return ans


class Solution:

	def displayContacts(self, n, contact, s):

		class TrieNode:

			def __init__(self):
				self.child = {}
				self.Eow = False

		def insert(word, Trie):
			for i in word:
				if i not in Trie.child:
					Trie.child[i] = TrieNode()
				Trie = Trie.child[i]
			Trie.Eow = True

		def dfs(prefix, Trie, res):
			if Trie.Eow:
				res.append(prefix)
			for c in Trie.child:
				prefix = prefix + c
				dfs(prefix, Trie.child[c], res)
				prefix = prefix[:-1]

		def prefix_search(prefix, Trie):
			res = []
			for i in prefix:
				if i in Trie.child:
					Trie = Trie.child[i]
				else:
					return ['0']
			dfs(prefix, Trie, res)
			return res
		Trie = TrieNode()
		for i in contact:
			insert(i, Trie)
		Final = []
		for j in range(len(s)):
			r = prefix_search(s[:j + 1], Trie)
			r.sort()
			Final.append(r)
		return Final


class Solution:

	def displayContacts(self, n, contact, s):
		newString = ''
		result = []
		for i in range(0, len(s)):
			row = []
			newString = newString + s[i]
			for x in range(0, n):
				if contact[x].find(newString) != -1:
					row.append(contact[x])
			row = list(set(row))
			list.sort(row)
			if len(row) != 0:
				result.append(row)
			else:
				result.append('0')
		return result