There are n phone numbers in Polycarp's contacts on his phone. Each number is a 9-digit integer, starting with a digit different from 0. All the numbers are distinct.

There is the latest version of Berdroid OS installed on Polycarp's phone. If some number is entered, is shows up all the numbers in the contacts for which there is a substring equal to the entered sequence of digits. For example, is there are three phone numbers in Polycarp's contacts: 123456789, 100000000 and 100123456, then:

  if he enters 00 two numbers will show up: 100000000 and 100123456,  if he enters 123 two numbers will show up 123456789 and 100123456,  if he enters 01 there will be only one number 100123456. 

For each of the phone numbers in Polycarp's contacts, find the minimum in length sequence of digits such that if Polycarp enters this sequence, Berdroid shows this only phone number.


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 70000) — the total number of phone contacts in Polycarp's contacts.

The phone numbers follow, one in each line. Each number is a positive 9-digit integer starting with a digit from 1 to 9. All the numbers are distinct.


-----Output-----

Print exactly n lines: the i-th of them should contain the shortest non-empty sequence of digits, such that if Polycarp enters it, the Berdroid OS shows up only the i-th number from the contacts. If there are several such sequences, print any of them.


-----Examples-----
Input
3
123456789
100000000
100123456

Output
9
000
01

Input
4
123456789
193456789
134567819
934567891

Output
2
193
81
91

Difficulty: MEDIUM

Starter code:

Solutions:
n = int(input())
maps = {}
for i in range(n):
	string = input()
	for j in range(len(string)):
		for a in range(0, j + 1):
			substr = string[a:j + 1]
			if substr not in maps:
				maps[substr] = {'index': i, 'count': 1}
			elif i != maps[substr]['index']:
				maps[substr]['count'] += 1
maps = sorted(maps.items(), key=lambda i: i[1]['index'])
count = 0
min_v = ''
min_count = 10
for (k, value) in maps:
	if count < value['index']:
		count += 1
		print(min_v)
		min_v = 'idk'
		min_count = 10
	if value['count'] == 1:
		if len(k) < min_count:
			min_count = len(k)
			min_v = k
print(min_v)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
l = []
for i in range(n):
	l.append(input())
from collections import defaultdict
d = defaultdict(int)
d1 = defaultdict(list)
for i in range(n):
	d2 = defaultdict(int)
	for j in range(9):
		s = l[i][j]
		if d2[s] == 0:
			d[s] += 1
			d2[s] += 1
		d1[i].append(s)
		for k in range(j + 1, 9):
			s += l[i][k]
			if d2[s] == 0:
				d[s] += 1
				d2[s] += 1
			if d[s] == 1:
				d1[i].append(s)
	d1[i].sort(key=len)
for i in range(n):
	for j in d1[i]:
		if d[j] == 1:
			print(j)
			break


n = int(input())
a = []
d = {}
for b in range(n):
	s = input()
	g = set()
	for i in range(len(s)):
		for k in range(i, len(s)):
			w = s[i:k + 1]
			if w in g:
				continue
			else:
				g.add(w)
			if w in d:
				d[w] += 1
			else:
				d[w] = 1
	a.append(s)
for s in a:
	ans = s
	for i in range(len(s)):
		for j in range(i, len(s)):
			k = s[i:j + 1]
			if d[k] == 1 and len(k) < len(ans):
				ans = k
	print(ans)


def rec(i):
	global a
	return i
import sys
from collections import Counter
sys.setrecursionlimit(10 ** 6)
n = int(input())
a = [input() for i in range(n)]
b = []
a0 = set()
c0 = set()
for i in a:
	c = set()
	for i0 in range(1, 10):
		for i1 in range(0, 10 - i0):
			c.add(i[i1:i1 + i0])
	b.append(c)
	c0.update(a0 & c)
	a0.update(c)
for i in b:
	c = i - c0
	z = '0' * 10
	for i0 in c:
		if len(i0) < len(z):
			z = i0
	print(z)


n = int(input())
l = []
for i in range(n):
	l.append(input())
d = {}
for k in l:
	for i in range(1, 9 + 1):
		for j in range(9 - i + 1):
			a = k[j:j + i]
			z = d.keys()
			if a in z:
				if k != d.get(a)[1]:
					w = d.get(a)
					w[0] += 1
					w[1] = k
					d.update({a: w})
			else:
				d.update({a: [1, k]})
r = list(d.items())
ans = []
for i in r:
	if i[1][0] == 1:
		ans.append([i[0], i[1][1]])
d1 = {}
for i in ans:
	z = d1.keys()
	if i[1] in z:
		if len(str(i[0])) < len(str(d1.get(i[1]))):
			d1.update({i[1]: i[0]})
	else:
		d1.update({i[1]: i[0]})
for i in l:
	print(d1.get(i))


def podstroki(s):
	return sorted(set((s[i:i1] for i in range(9) for i1 in range(i + 1, 10))), key=len)
res = {}
spisok = [podstroki(input()) for i in range(int(input()))]
for s in spisok:
	for podstr in s:
		if podstr in res:
			res[podstr] += 1
		else:
			res[podstr] = 1
for s in spisok:
	for podstr in s:
		if res[podstr] == 1:
			print(podstr)
			break


import sys
from collections import defaultdict

def input():
	return sys.stdin.readline()

def print(arg, *argv, end=None):
	sys.stdout.write(str(arg))
	for i in argv:
		sys.stdout.write(' ' + str(i))
	sys.stdout.write(end) if end or end == '' else sys.stdout.write('\n')

def mapi():
	return map(int, input().split())

def maps():
	return map(str, input().split())

def solve():
	t = 1
	for _ in range(t):
		n = int(input())
		ss = []
		a = []
		mem = defaultdict(int)
		for __ in range(n):
			x = input().strip()
			a.append(x)
			sett = set()
			for i in range(9):
				for j in range(i + 1, 10):
					sett.add(x[i:j])
			for it in sett:
				mem[it] += 1
		for id in range(n):
			length = 1
			flag = True
			while length < 10 and flag:
				i = 0
				j = length
				while i < 9 and j < 10:
					tmp = a[id][i:j]
					if mem[tmp] == 1:
						print(tmp)
						flag = False
						break
					i += 1
					j += 1
				length += 1

def __starting_point():
	solve()
__starting_point()


n = int(input())
num = []
for i in range(n):
	num.append(input())
d = {}
q = []
for i in range(n):
	r = {}
	g = []
	for j in range(0, 9):
		for l in range(j + 1, 10):
			t = num[i][j:l]
			g.append(t)
			if t in r:
				continue
			r[t] = 1
			if t in d:
				d[t] = d[t] + 1
			else:
				d[t] = 1
	g.sort(key=len)
	q.append(g)
if n == 1:
	print(num[0][0])
	exit(0)
answ = []
for i in range(n):
	for j in q[i]:
		if d[j] == 1:
			answ.append(j)
			break
for i in answ:
	print(i)


n = int(input())
numbers = []
for i in range(0, n):
	number = input()
	numbers.append(number)
telep = {}
count = 1
for number in numbers:
	for l in range(1, len(number) + 1):
		for i in range(0, len(number) - l + 1):
			key = number[i:i + l]
			if key in telep and telep[key] != count:
				telep[key] = -1
			else:
				telep[key] = count
	count += 1
reverse = {}
for key in telep:
	if telep[key] == -1:
		continue
	elif telep[key] not in reverse:
		reverse[telep[key]] = key
	elif len(key) < len(reverse[telep[key]]):
		reverse[telep[key]] = key
for i in range(1, n + 1):
	print(reverse[i])


n = int(input())
(s, p) = ({}, [''] * n)
for k in range(n):
	p[k] = input()
	for q in [p[k][i:j] for i in range(9) for j in range(i + 1, 10)]:
		s[q] = -1 if q in s and s[q] != k else k
for (q, k) in list(s.items()):
	if ~k and len(p[k]) > len(q):
		p[k] = q
print('\n'.join(p))


n = int(input())
m = {}
a = []
for i in range(n):
	s = input()
	sub = set()
	for i in range(len(s)):
		for j in range(i, len(s)):
			k = s[i:j + 1]
			if k in sub:
				continue
			else:
				sub.add(k)
			if k in m:
				m[k] += 1
			else:
				m[k] = 1
	a.append(s)
for s in a:
	ans = s
	for i in range(len(s)):
		for j in range(i, len(s)):
			k = s[i:j + 1]
			if m[k] == 1 and len(k) < len(ans):
				ans = k
	print(ans)


indexs = []
for length in range(1, 10):
	for start in range(0, 9 - length + 1):
		indexs.append([start, start + length])
n = int(input())
used = {}
s = []
for i in range(n):
	s.append(input())
	for un in set((s[-1][index[0]:index[1]] for index in indexs)):
		used[un] = used.get(un, 0) + 1
for num in s:
	for index in indexs:
		if used[num[index[0]:index[1]]] == 1:
			print(num[index[0]:index[1]])
			break


from collections import defaultdict

def subs(s):
	for l in range(1, len(s) + 1):
		for shift in range(0, len(s) - l + 1):
			yield s[shift:shift + l]
n = int(input())
vs = [input() for _ in range(n)]
entries = defaultdict(set)
for (i, s) in enumerate(vs):
	for sub in subs(s):
		entries[sub].add(i)
for s in vs:
	for sub in subs(s):
		if len(entries[sub]) == 1:
			print(sub)
			break


n = int(input())
mass = []
for i in range(n):
	a = input()
	mass.append(a)
a = dict()
for i in range(len(mass)):
	for j in range(len(mass[i])):
		for k in range(j + 1, len(mass[i]) + 1):
			if mass[i][j:k] in a:
				if a[mass[i][j:k]][1] != i:
					a[mass[i][j:k]][0] += 1
					a[mass[i][j:k]][1] = i
			else:
				a[mass[i][j:k]] = [1, i]
for i in range(len(mass)):
	ans = '1' * 11
	for j in range(len(mass[i])):
		for k in range(j + 1, len(mass[i]) + 1):
			if a[mass[i][j:k]][0] == 1:
				if k - j < len(ans):
					ans = mass[i][j:k]
	print(ans)


n = int(input())
q = {}
z = [input() for i in range(n)]
for s in z:
	w = set()
	for i in range(len(s)):
		for j in range(i, len(s)):
			k = s[i:j + 1]
			if k in w:
				continue
			else:
				w.add(k)
			if k in q:
				q[k] += 1
			else:
				q[k] = 1
for s in z:
	r = s
	for i in range(len(s)):
		for j in range(i, len(s)):
			k = s[i:j + 1]
			if q[k] == 1 and len(k) < len(r):
				r = k
	print(r)


import sys
from collections import defaultdict
N = int(input())
S = []
Subs = defaultdict(int)
for i in range(N):
	s = input()
	S.append(s)
	for ff in range(1, 10):
		for ss in range(10 - ff):
			Subs[s[ss:ss + ff]] += 1
for i in range(N):
	flag = 0
	At = S[i]
	for ff in range(1, 10):
		curr = defaultdict(int)
		for ss in range(10 - ff):
			curr[At[ss:ss + ff]] += 1
		for key in list(curr.keys()):
			if curr[key] == Subs[key]:
				print(key)
				flag = 1
				break
		if flag:
			break


h = [(i, j) for i in range(9) for j in range(i + 1, 10)]
n = int(input())
(s, p) = ({}, [''] * n)
for k in range(n):
	t = input()
	for q in [t[i:j] for (i, j) in h]:
		s[q] = -1 if q in s and s[q] != k else k
for (q, k) in s.items():
	if k >= 0:
		if p[k]:
			if len(p[k]) > len(q):
				p[k] = q
		else:
			p[k] = q
print('\n'.join(p))


import math
from collections import *
a = int(input())
indx = defaultdict(list)
done = defaultdict(list)
for t in range(a):
	s = input()
	for i in range(len(s)):
		for j in range(i, len(s)):
			m = s[i:j + 1]
			if len(done[m]) == 0:
				done[m].append(t)
				indx[t].append(m)
			elif len(done[m]) == 1 and done[m][0] != math.inf and (t != done[m][0]):
				indx[done[m][0]].remove(m)
				done[m][0] = math.inf
for i in range(a):
	af = indx[i]
	mini = 15
	ss = ''
	for i in range(len(af)):
		if len(af[i]) < mini:
			mini = len(af[i])
			ss = af[i]
	print(ss)