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

Starter code:

Solutions:
def rec(i):
    nonlocal a
    return i
import sys
from collections import Counter
sys.setrecursionlimit(10**6)
n=int(input())
#n,m=list(map(int,input().split()))
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)


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


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

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

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


n = int(input())
numbers = [input() for i in range(n)]
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])
        


def nash():
    n = int(input())
    numbers = [input() for i in range(n)]
    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])
nash()
        


def nash():
    n = int(input())
    numbers = [input() for i in range(n)]
    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])
nash()
        


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)



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


n = int(input())
mass = []
for i in range(n):
    a = input()
    mass.append(a)
# 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):
#             cnt = 0
#             for l in range(len(mass)):
#                 if l != i:
#                     if mass[i][j:k] not in mass[l]:
#                         cnt += 1
#                     else:
#                         break
#             if cnt == n - 1:
#                 if k - j < len(ans):
#                     ans = mass[i][j:k]
#     print(ans)

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]
# print(a)
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())
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])
    return
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)

"""
-----------------------------Pseudo---------------------------------
"""
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
    #t = int(input())
    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())
a=[]
d={}

for _ in range(n):
    s=input()
    g=set()
    for i in range(len(s)):
        for k in range(i,len(s)):
            st=s[i:k+1]
            if st in g:
                continue
            else:
                g.add(st)
            if st in d:
                d[st]+=1
            else:
                d[st]=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)


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}
            else:
                if 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 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)
            else:
                if(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)
        


        
        


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

            
            
            
            
            
            


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
        # Here we check
        for key in list(curr.keys()):
            if(curr[key] == Subs[key]):
                print(key)
                flag = 1
                break
        if(flag):
            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)