Sandy is a professor at a very reputed institute. The institute mandates that all the lectures be communicated in English. As Sandy is not very good at English(or anything actually) the presentations he displays in class have a lot of spelling mistakes in them.
As you have a dictionary on you containing $N$ words in it, the responsibility of correctly deducing the misspelt word falls upon your shoulders. Sandy's presentation contains in them, $Q$ words which you $think$ are wrongly spelt. A word is misspelt if a $single$ letter in it is missing or is different from the corresponding correctly spelled word in your dictionary.
For each of the misspelt word in the presentation find out the corresponding correct word from your dictionary.
Note : 
- For each misspelt word in Sandy's presentation, there exists one and only one correctly spelt word in your dictionary that corresponds to it. 
- Out of the $Q$ misspelt words given to you, there might be some which are correctly spelt i.e., that word completely matches a word in your dictionary. (Give Sandy some credit, he's a teacher after all). For such words print the word corresponding to it in your dictionary.
- The maximum length of each string can be $L$.

-----Input:-----
- First line contains a single integer $T$ denoting the number of testcases. Then the testcases follow. 
- The first line of each test case contains two space-separated integers $N, Q$ corresponding to the number of words in your dictionary and the number of misspelt word in Sandy's dictionary respectively.
- $N$ lines follow each containing a single string $S$ denoting a word in your dictionary.
- $Q$ lines follow each containing a single string $M$ denoting a misspelt word in Sandy's presentation.

-----Output:-----
In each testcase, for each of the $Q$ misspelt words, print a single word $S$ corresponding to the correctly spelt word in your dictionary.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 200$
- $1 \leq Q \leq 200$
- $1 \leq L \leq 100$
- None of the words contain any spaces in them.
- Each letter in every word is in lower case.

-----Subtasks-----
- 
Subtask 1 : 10 points
- $1 \leq N \leq 50$
- $1 \leq Q \leq 10$
- 
Subtask 2 : 90 points
- Original Constraints

-----Sample Input:-----
1
5 2
szhbdvrngk
qzhxibnuec
jfsalpwfkospl
levjehdkjy
wdfhzgatuh
szhbdvcngk
qzhxbnuec

-----Sample Output:-----
szhbdvrngk
qzhxibnuec

-----EXPLANATION:-----
- In the first misspelt word $szhbdvcngk$, a single letter $c$ is different from the original word $szhbdvrngk$.
- The second misspelt word $qzhxbnuec$ is missing the letter $i$ that  was in the original word $qzhxibnuec$.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from difflib import get_close_matches
import sys, os

def closeMatches(patterns, word):
	return get_close_matches(word, patterns, 1, 0.9)[0]

def get_string():
	return sys.stdin.readline().strip()

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
ans = []
test = int(input())
for i in range(test):
	(n, q) = get_ints()
	n = int(n)
	q = int(q)
	patterns = []
	for j in range(n):
		s = get_string()
		patterns.append(s)
	for j in range(q):
		word = get_string()
		ans.append(closeMatches(patterns, word))
for j in ans:
	sys.stdout.write(j + '\n')


t = int(input())
while t > 0:
	line = input().split()
	n = int(line[0])
	q = int(line[1])
	mylist = []
	while n > 0:
		s = input().strip()
		mylist.append(s)
		n -= 1
	while q > 0:
		m = input().strip()
		if m in mylist:
			print(m)
		else:
			for item in mylist:
				i = 0
				if len(item) == len(m):
					while i < len(m) and item[i] == m[i]:
						i += 1
					i += 1
					if item[i:len(item) - 1] == m[i:len(m) - 1]:
						print(item)
						break
				else:
					while i < len(m) and item[i] == m[i]:
						i += 1
					if item[i + 1:len(item) - 1] == m[i:len(m) - 1]:
						print(item)
						break
		q -= 1
	t -= 1


from difflib import get_close_matches
import sys

def closeMatches(patterns, word):
	print(get_close_matches(word, patterns, 1, 0.9)[0])

def get_string():
	return sys.stdin.readline().strip()
test = int(input())
for i in range(test):
	(n, q) = input().split(' ')
	n = int(n)
	q = int(q)
	patterns = []
	for i in range(n):
		s = get_string()
		patterns.append(s)
	for i in range(q):
		word = get_string()
		closeMatches(patterns, word)


for i in range(int(input())):
	(n, q) = list(map(int, input().split()))
	dicword = []
	misp = []
	for j in range(n):
		dicword.append(input())
	for j in range(q):
		misp.append(input())
	for j in range(len(misp)):
		temp = misp[j]
		for k in dicword:
			err = 0
			if len(k) == len(temp) + 1:
				huh = 0
				for l in range(len(temp)):
					if temp[l] != k[l + huh]:
						if temp[l] == k[l + 1]:
							huh += 1
							err += 1
						else:
							err += 1
					if err > 1 or huh > 1:
						break
				if err <= 1:
					print(k)
					break
			elif len(k) == len(temp):
				for l in range(len(temp)):
					if temp[l] != k[l]:
						err += 1
					if err > 1:
						break
				if err <= 1:
					print(k)
					break
			else:
				pass


for i in range(int(input())):
	(n, q) = map(int, input().split())
	nn = []
	qq = []
	for j in range(n):
		nn.append(input())
	for j in range(q):
		qq.append(input())
	for j in qq:
		l3 = []
		for k in nn:
			if len(j) < 4:
				(a, b) = (1, 1)
			elif len(j) < 20:
				(a, b) = (2, 1)
			elif len(j) < 40:
				(a, b) = (3, 2)
			elif len(j) <= 100:
				(a, b) = (5, 4)
			m = 0
			for l in range(0, len(j), b):
				try:
					d = j[l:l + a]
					m += k.count(j[l:l + a])
				except IndexError:
					break
			l3.append(m)
		print(nn[l3.index(max(l3))])


from collections import Counter
test = int(input())
for _ in range(test):
	(n, q) = list(map(int, input().split(' ')))
	correct = []
	allcorrect = []
	allwrong = []
	wrong = []
	for j in range(n):
		mydict = input()
		if mydict not in correct:
			correct.append(mydict)
	for f in range(len(correct)):
		allcorrect.append(Counter(correct[f]))
	for i in range(q):
		misspelt = input()
		wrong.append(misspelt)
	for s in range(len(wrong)):
		allwrong.append(Counter(wrong[s]))
	for k in range(len(wrong)):
		for j in range(len(correct)):
			value = allwrong[k] - allcorrect[j]
			if len(value) == 1:
				print(correct[j])
			if len(value) == 0:
				print(correct[j])


from difflib import get_close_matches
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	mydic = {}
	vis = {}
	for i in range(n):
		temp = input()
		mydic[temp] = 1
	for i in range(q):
		temp = input()
		if temp in mydic.keys():
			print(temp)
		else:
			x = get_close_matches(temp, mydic.keys(), cutoff=0.7)
			if len(x) > 0:
				mydic.pop(x[0])
				vis[x[0]] = 1
				print(x[0])
			else:
				print(get_close_matches(temp, vis.keys(), cutoff=0.7)[0])