problem-1-8

Steve Jobs' ghost has come down to BITS Pilani Hyderabad Campus, since he has heard a lot about the coding culture here. Hoping to recruit talented people to work on top-secret Apple software, he keeps a strict coding test.

Apple is currently working on a upgraded version of a automated form filler. They call it the iComplete application. Steve Jobs is looking for BPHC talent to work on it.

Therefore, his coding test requires contestants to work on a basic iComplete application.

iComplete V1.0 is an application that works by receiving part of a word and automatically completing it depending on the dictionary present on the device. Therefore for the coding test, you are given a dictionary of n words. Now Steve Jobs will come over to your machine and type a string s. Your task is to complete s to match one of the words in the dictionary.

In case many words have s as a prefix, you have to find the lexicographically smallest word amongst these. In case no match is found, simply return the string s.

Input

The first line contains the string s which Steve Jobs' ghost types. The second line contains an integer n (1 ≤ n ≤ 100) which is the number of words in the dictionary. Then follow n lines which are the words on the dictionary, one on each line. All the lines have lengths of 1 to 100 characters inclusively, and consist of lowercase English letters only.
Output
If s is not the beginning of any of n words in the dictionary, print s. Otherwise, print the lexicographically lowest word beginning with s.

The lexicographical order is the order of words in a dictionary.

Sample test(s)
Input
next
2
nextpermutation
nextelement

Output
nextelement

Input
find
4
find
findfirstof
findit
fand

Output
find

Input
find
4
fondfind
fondfirstof
fondit
fand

Output
find

SAMPLE INPUT
next
2
nextpermutation
nextelement

SAMPLE OUTPUT
nextelement

Explanation

Since nextelement is smaller when seen in dictionary, it is preferred over nextpermutation.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
w = input()
leastLen = 10000000
n = eval(input())
temp = w
while n:
	n -= 1
	a = input()
	if len(a) <= leastLen and a[:len(w)] == w:
		if len(a) == len(w):
			temp = a
			break
			
		temp = a
		leastLen = len(a)
	
print(temp)


import sys

def get_line():
	return sys.stdin.readline().rstrip()

partial = get_line()

words = int(get_line())

shortestMatch = None

while words > 0:
	words -= 1
	
	word = get_line()
	
	if shortestMatch is not None and len(shortestMatch) < len(word):
		continue
	
	if len(word) < len(partial):
		continue
	
	if word.startswith(partial):
		shortestMatch = word
		
print(shortestMatch or partial)


w=input()
n=eval(input())
l=list()
for i in range(0,n):
	a=input()
	l.append(a)

le=0
s=-1
for j in range(0,n):
	if w==str(l[j]):
		s=j
		break
	if(str(l[j]).find(w,0,len(l[j]))==0):
		if(le==0):
			
			le=len(str(l[j]))
			s=j
		else:
			if(le>len(l[j])):
				le=len(l[j]);
				s=j
		
if s==-1:
	print(w)
else:
	print(l[s])
			


from string import ascii_lowercase
from collections import OrderedDict

od = OrderedDict((ch, idx) for idx, ch in enumerate(ascii_lowercase, 1))



class check():
	def __init__(self,name,name_array):
		self.name=name
		self.name_array=name_array
		self.name_array_2=[]
		self.max=len(name)
		self.name_array_len=len(name_array)
		self.r=''
		self.b=True
		self.ret()
	def ret(self):
		for i in range(0,self.name_array_len):
			if (self.name_array[i]==self.name):
				print(self.name_array[i])
				return 0
		for i in range(0,self.name_array_len):
			if(len(self.name_array[i])>len(self.name) and self.name_array[i][0:len(self.name)]==self.name):
				self.name_array_2.append(self.name_array[i])
		self.name_array=list(self.name_array_2)
		
		if(len(self.name_array)==0):
			print(self.name)
			return 0
		if(len(self.name_array)==1):
			print(self.name_array[0])
			return 0

		print(sorted(self.name_array)[0])
		return 0
						 
						
	   
name=input()        
name_array_len=eval(input())
name_array=[]
for i in range(0,name_array_len):
	name_array.append(input())
check(name,name_array)




class ourclass():
	def icomplete():
		required= input()
		number= int(input())
		dict=[]
		for i in range(number):
			dict.append(input())
		ans= []
	
		for j in range(len(dict)):
			if required== dict[j][:len(required)]:
				ans.append(dict[j])
	
		if len(ans)>0:
			print((min(ans)))
			return min(ans)
		print(required)
		return required
	icomplete()


from string import ascii_lowercase
from collections import OrderedDict

od = OrderedDict((ch, idx) for idx, ch in enumerate(ascii_lowercase, 1))



class check():
	def __init__(self,name,name_array):
		self.name=name
		self.name_array=name_array
		self.name_array_2=[]
		self.max=len(name)
		self.name_array_len=len(name_array)
		self.r=''
		self.b=True
		self.ret()
	def ret(self):
		for i in range(0,self.name_array_len):
			if (self.name_array[i]==self.name):
				print(self.name_array[i])
				return 0
		for i in range(0,self.name_array_len):
			if(len(self.name_array[i])>len(self.name) and self.name_array[i][0:len(self.name)]==self.name):
				self.name_array_2.append(self.name_array[i])
		self.name_array=list(self.name_array_2)
		
		if(len(self.name_array)==0):
			print(self.name)
			return 0
		if(len(self.name_array)==1):
			print(self.name_array[0])
			return 0

		for i in range(0,len(self.name_array)-1):
			if(len(self.name_array[i])>len(self.name_array[i+1])):
				self.max=len(self.name_array[i])
					
			else:
				self.max=len(self.name_array[i+1])
					
		for i in range(0,self.max):
			if(self.b):
				for p in range(0,len(self.name_array)-2 ):    
					if((len(self.name_array[p])>len(self.name)+i)and (len(self.name_array[p+1])>len(self.name)+i)):
							if(od[(self.name_array[p][len(self.name)+i])]<od[(self.name_array[p+1][len(self.name)+i])]):
								self.r=self.name_array[p]
								self.b=False
							elif(od[(self.name_array[p][len(self.name)+i])]>od[(self.name_array[p+1][len(self.name)+i])]):
								self.r=self.name_array[p+1]
								self.b=False
							else:
								self.b=True
					elif((len(self.name_array[p]))==(len(self.name)+i)):
							print(self.name_array[p])
							return 0
					elif((len(self.name_array[p+1]))==(len(self.name)+i)):
							print(self.name_array[p+1])
							return 0
			elif(self.b==False):
				print(self.r)
				return 0
						 
						
	   
name=input()        
name_array_len=eval(input())
name_array=[]
for i in range(0,name_array_len):
	name_array.append(input())
check(name,name_array)




#sdasda 
check=input()
x=eval(input())
dict=[input() for i in range(0,x)]
result=[]
for i in range(0,x):
	element=dict[i]
	if element.startswith(check):
		result.append(element)
		
result.sort()
if (not result):
	print(check)
else:
	print(result[0])

	


s=input()
l=[]
for p in range(eval(input())):
	l.append(input())
l.sort()
#print l
flag=0
for i in l:
	if s in i[:len(s)+1]:
		print(i)
		flag=1
		break
if flag==0:
	print(s)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
w = input()
T = int(input())
l = []
flag = False
while(T):
	l.append(input())
	T = T-1
l.sort()
for i in l:
	if i.startswith(w):
		flag = True
		print(i)
		break
if not flag:
	print(w)


s=input()
n=int(input())
arr=[]
class pres(object):
	def __init__(self,w,p):
		self.w=w
		self.p=p
for i in range(n):
	inp=input()
	arr.append(pres(inp,True))
for i in range(n):
	temp=arr[i].w
	sl=temp[:len(s)]
	if s!=sl:
		arr[i].p=False  
arr=[rep for rep in arr if rep.p==True]
k=True
if len(arr)==0:
	print(s)
	k=False
if k:
	for temp in arr:
		if temp.w==s:
			print(s)
			k=False
narr=[]
q=False
if k:
	for i in range(len(arr)):
		narr.append(arr[i].w[len(s):])
	short=0
	for i in range(len(narr)):
		if len(narr[short])>len(narr[i]):
			short=i
	for i in range(len(narr[short])):
		for j in range(len(narr)):
			for k in range(len(narr)-1):
				if ord(narr[k][i])>ord(narr[k+1][i]):
					   temp=narr[k]
					   narr[k]=narr[k+1]
					   narr[k+1]=temp
			
	print(s+narr[0])


check=input()
x=eval(input())
dict=[input() for i in range(0,x)]
result=[]
for i in range(0,x):
	element=dict[i]
	if element.startswith(check):
		result.append(element)
		
result.sort()
if (not result):
	print(check)
else:
	print(result[0])

	  


s = input()
A = []
for i in range(eval(input())):
	A.append(input())
A.sort()
for x in A:
	if x.startswith(s):
		print(x)
		break
else:
	print(s)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
dic=[]
arr=[]
length=[]
word=input()
n=int(input())
for i in range(0,n):
	w=input()
	dic.append(w)
for w in dic:
	if word in w:
		q=len(word)
		if w[0:q]==word:
			w=w.replace('word','')
			arr.append(w)
			length.append(len(w))
if len(arr)!=0:	
	min_len=min(length)
	index=length.index(min_len)
	print(arr[index])
else:
	print(word)