63_1_Sec5_Q1 (71)
# 6331301521 1287928 (2020-11-17 09:56)
line = input().strip().lower()
n = int(input())
dc=[]
for i in range(n):
    dc.append(input())
    
sen = '' 
long = []
nf = True
i = 0
while i < len(line):
    search = line[i:]
    for j in range(1,len(search)+1):
        if search[:j] in dc:
            long.append(search[:j])
    if long != []:
        lw = long[0]
        for k in long:
            if len(k) > len(lw):
                lw = k
        sen += lw + ' '
        i += len(lw)
        nf = False
    else:
        if nf == False:
            sen += line[i] + ' '
        elif nf == True:
            sen = sen[:-1] + line[i] + ' '
        nf = True
        i += 1
    long = []
    
print(sen)


# 6331302121 1295974 (2020-12-04 22:26)
s = input().strip()
s = s.lower()
n = int(input())
d = dict()
for i in range(n):
    w = input().strip()
    d[i] = w
ans = ''
while len(s) > 0:
    c = ''
    for k in d:
        if s[0] != d[k][0]:
            pass
        else:
            if s[:len(d[k])] == d[k]:
                if len(c) < len(d[k]):
                    c = d[k]
    if len(c) > 0:
        ans = ans.strip()
        ans+=' ' + c + ' '
        s = s[len(c):]
    else:
        ans+=s[0]
        s = s[1:]
ans = ans.strip()
print(ans)

# 6331303821 1288049 (2020-11-17 10:25)
text=input().lower()
n=int(input())
dict=[]
for i in range(n):
    x=str(input())
    dict.append(x)
for i in range(n):
    for j in range(n-1):
        if len(dict[j])<len(dict[j+1]) :
            dict[j],dict[j+1]=dict[j+1],dict[j]
check=''
ans=[]
while len(text)>0 :
    found=False
    check=text
    for i in range(len(text)) :
        if i!=0 :
            check=text[:0-i]
        for j in range(len(dict)) :
            if check== dict[j] :
                ans.append(dict[j])
                found=True
                text=text[len(text)-i:]
                break
        if found :
            break
    if not found :
        ans.append(text[0])
        text=text[1:]

for i in range(len(ans)) :
    if len(ans[i])==1 and (ans[i] not in dict) and (i+1)<len(ans)  :
        if ans[i+1] in dict :
            print(ans[i],end=' ')
        else :
            print(ans[i],end='')
    elif len(ans[i])==1 and (ans[i] not in dict) :
        print(ans[i],end='')
    else :
        print(ans[i],end=' ')

# 6331304421 1295733 (2020-12-04 18:58)
######
# Here is a bug

'''
appy
2
p
pp
'''

dicts = dict()

line = input()

n = int(input())

for _ in range(n):
    x = input()
    # ดักโล่งๆ
    if x:
        if x[0] not in dicts:
            dicts[x[0]] = [x]
        else:
            dicts[x[0]].append(x)

word_list = list()

word = ''

while line:
    if line[0] in dicts:
        longest_word = ''
        
        for w in dicts[line[0]]:

            if len(w) > len(longest_word) and line[0:len(w)] == w:
                longest_word = w
        
        if longest_word:

            if word:
                word_list.append(word)
                word = ''
                word_list.append(longest_word)
                line = line[len(longest_word)::]

            else:
                word_list.append(longest_word)
                line = line[len(longest_word)::]
        
        else:
            word += line[0]
            line = line[1::]

    else:
        word += line[0]
        line = line[1:]

if word:
    word_list.append(word)
    
print(' '.join(word_list))


# 6331306721 1296142 (2020-12-05 11:22)
data = input().lower()
n = int(input())
dic = [input() for _ in range(n)]
result = ''

while len(data) > 0:
    longest = ''
    for i in range(len(data)):
        if data[:i+1] in dic:
            longest = data[:i+1]
    if longest == '':
        result += data[0]
        data = data[1:]
    else:
        result = result.strip()
        result += ' ' + longest + ' '
        data = data[len(longest):]

print(result.strip())


# 6331307321 1288164 (2020-11-17 10:48)
word=input().strip()
n=int(input())
dict={}
longest=[]
for i in range(n):
    words=input()
    length = len(words)
    if length not in longest:
        longest.append(length)
        dict[length]=[]
    dict[length].append(words)    
longest.sort(reverse=True)
output=''
i=0
while i <len(word):
    found=False
    for e in longest:
        if word[i:i+e] in dict[e]:
            output+=' '+word[i:i+e]+' '
            i+=e
            found=True
        if found:
            break
    if not found:
        output+=word[i]
        i+=1
print(output)
'''out=[]
idxs=[]
temp=word
for e in longest:
    for wordss in dict[e]:
        if wordss in temp:
            idx=word.index(wordss)
            out.append(wordss)
            idxs.append(idx)
            temp=word[:idx]+word[idx+e:]
temp=[]
output=''
for e in temp:
    
for i in range(len(word)):
    if i != temp[chk]:'''
    
            


# 6331308021 1288386 (2020-11-17 11:10)
text = input().strip().lower().replace(' ','')
text2 = text
n = int(input())
d = []
for i in range(n):
    y = input().lower()
    x = len(y)
    for i in range(len(text)):
        d.append([-x,y])
d.sort()
r = []
def cut(text,d,r):
    for e in d:
        if e[1] in text:
            pos = text.find(e[1])
            text = text[:text.find(e[1])]+' '*len(e[1])\
                       + text[text.find(e[1])+len(e[1]):]
            r.append([pos,e[1]])
            d.remove(e)
            return cut(text,d,r)
    return text.strip().split()
text = cut(text,d,r)
for e in text:
    if e != ' ':
        r.append([text2.find(e),e])
r.sort()
out = []
for k,v in r:
    out.append(v)
print(' '.join(out))
                   
    

# 6331309621 1295719 (2020-12-04 18:52)
txt = input().strip()
n = int(input())
dic = {}
for i in range(n):
    inf = input().strip()
    if inf[0] in dic:
        dic[inf[0]].append(inf)
    else:
        dic[inf[0]] = []
        dic[inf[0]].append(inf)
ans = []
st = ''
while len(txt) > 0:
    pro = [] 
    start = txt[0]
    if start in dic:
        for e in dic[start]:
            if txt[:len(e)] == e:
                pro.append([len(e),e])
                ans.append(st)
                st = ''
        if len(pro) > 0:
            pro.sort(reverse = 1)
            ans.append(pro[0][1])
            txt = txt[pro[0][0]:]
    
        else:
            st+= start
            txt = txt[1:]
    else:
        st+= start
        txt = txt[1:]
ans.append(st)
for e in ans:
    if e == '':
        ans.remove(e)
print(' '.join(ans))             
    
    


# 6331310121 1288193 (2020-11-17 10:52)
t = input()
n = int(input())
d = sorted([input() for _ in range(n)])
d = sorted(d, key = lambda x:len(x), reverse = True)
p = [0 for _ in range(len(t))]
l = 1
for k in d:
    m = t.count(k)
    last = -1
    while m > 0:
        start = t.find(k,last + 1)
        if p[start:start+len(k)] == [0] * len(k):
            p[start:start+len(k)] = [l] * len(k)
            l += 1
        last = start
        m = m-1
output = t[0]
for i in range(1, len(t)):
    if p[i] != p[i-1]:
        output += ' '
    output += t[i]
print(output)
        


# 6331311821 1295839 (2020-12-04 20:32)
text=input().lower()
n=int(input())
word=[]
t=''
out=[]
for i in range(n):
    a=input().lower()
    word.append(a)
while True:
    d=[]
    for i in range(1,len(text)+1):
        if text[0:i] in word:
            d.append(text[0:i])
    if d!=[]:
        l=[len(e) for e in d]
        pos=l.index(max(l))
        key=d[pos]
        for i in range(1,len(text)+1):
            if text[:i]==key:
                out.append(t)
                out.append(key)
                text=text[i:]
                t=''
                break
    else:
        t+=text[0]
        text=text[1:]
        if text=='':
            out.append(t)
    if text=='':break
print(' '.join([e for e in out if e!='']))

# 6331312421 1295662 (2020-12-04 17:46)
word = input().lower()
n=int(input())
Dic=[]
Answer=[]
p=0
hi=''
a=0
k=0
for i in range(n):
    Dic.append(input())
while a < len(word):
    for j in range(len(word)-a):
        for i in range(len(Dic)):
            if word[a:len(word)-j] == Dic[i]:
                if k>=1 :
                    Answer.append(Dic[i])
                    a+=len(Dic[i])
                    hi+=' '+Dic[i]+' '
                    p+=1
                    k=0
                    break
                if p >= 1 :
                    Answer.append(Dic[i])
                    a+=len(Dic[i])
                    hi+=Dic[i]+' '
                    p+=1
                    break
                if p == 0 and k == 0 :
                    Answer.append(Dic[i])
                    a+=len(Dic[i])
                    hi+=Dic[i]+' '
                    p+=1
                    break
    if Answer == [] :
        if p >= 1 and hi[-1] != ' ' :
            hi+=word[a]+' '
            a+=1
            p=0
        else:
            hi+=word[a]
            a+=1
            k+=1
            p=0
            
    Answer=[]
print(hi)
    



# 6331313021 1295632 (2020-12-04 16:21)
sentence=input().strip()
sentence=sentence.lower()
n=int(input())
dic=[]
for i in range(n):
    word=input().strip()
    dic.append(word)
start=0
dic.sort(key=lambda e: -len(e))
#print(dic)
new=""
unknown=""
while True:
#     print('n',new)
#     print('u',unknown)
#     print('s',sentence[start])
    found=False
    for i in range(len(dic)):
        if sentence.find(dic[i],start)==start:
            if unknown!="":
                new+=unknown+" "
                unknown=""
            new+=dic[i]+" "
            start+=len(dic[i])
            found=True
            break
    if start>=len(sentence):
        new+=unknown
        break
    if found==False:
        unknown+=sentence[start]
        start+=1
print(new)


# 6331314721 1296350 (2020-12-06 17:00)
a = input().lower()
n = int(input())
dicts = [input() for i in range(n)]
out = False
ans = []
x=''
while out == False:
  b=a
  for i in range(len(a)):
    if i == len(a)-1:
      x += a[0]
      a = a[1:]
    elif b not in dicts:
      b = b[:len(b)-1]
    elif b in dicts:
      if x == '':
        ans.append(b)
      else:
        ans.append(x)
        ans.append(b)
        x=''
      a = a[len(b):]
      break
  if len(a)==0:
    ans.append(x)
    out=True
for i in range(len(ans)):
  print(ans[i],end=' ')

# 6331315321 1295876 (2020-12-04 21:10)
lst = []
lst1 = []
ass = False
s = str(input()).lower()
n = int(input())
for i in range(n):
    z = input()
    lst.append([-len(z),z])
    lst1.append(z)
lst.sort()
ans = ""
for ta in lst1:
    if s.find(ta) != -1:
        ass = True
        break
while len(s) != 0 and ass:
    for j in lst:
        x = s.find(j[1])
        if x == 0:
            ans =ans.strip(".")
            ans += " " + s[0:len(j[1])]
            s = s[len(j[1]):]
            break
        elif j == lst[-1]:
            if len(ans) >0:
                if ans[-1] == ".":
                    ans = ans.strip(".")
                    ans += s[0] +"."
                    s = s[1:]
                else:
                    ans += " " + s[0] + "."
                    s =s[1:]
            else:
                ans += " " + s[0] + "."
                s =s[1:]
if ass == False:
    print(s)
else:
    ans = ans.strip(".")
    ans = ans.strip(" ")
    print(ans)

# 6331316021 1296184 (2020-12-05 12:41)
x=input().lower().strip()
n=int(input())
Dict=[]
for i in range(n):
    world=input().strip()
    Dict.append(world)
out=""
T=True

for i in range(len(x)):
    if T == False:
        c=d
    else:
        c=i
    for k in range(len(x)):
        R=True
        j=len(x)
        while R:
            if x[c:j] in Dict:
                out +=" "+x[c:j]+" "
                d=j
                T=False
                R=False
                
            elif j==(c+1)-len(x) or c+1==len(x):
                out +=x[c:c+1]
                d=c+1
                R=False
                
            j -=1
        if R == False:
            break
    if d==len(x):
        break
out=out.strip()
print(out)  
       


# 6331317621 1296482 (2020-12-07 13:00)
word = input()
n = int(input())
dic = []
ans = []
w = word
singlealp = ''
for i in range(n):
  x = input()
  dic.append(x)
while True:
  if len(w) == 0:
    ans.append(singlealp)
    break
  for i in range(len(w),0,-1):
    if w[:i] in dic:
      if singlealp == '':
        ans.append(w[:i])
        w = w[i:]
        break
      else:
        ans.append(singlealp)
        ans.append(w[:i])
        w = w[i:]
        singlealp = ''
        break
    elif i == 1 :
      singlealp += w[0]
      w = w[1:]
      break
print(' '.join(ans))

# 6331319921 1288636 (2020-11-17 11:28)
sentence = input()
sentence = sentence.lower()
n = int(input())
#สร้างdict
dict = {}
for i in range(n):
    word = input()
    if word[0] in dict:
        dict[word[0]].append(word)
    else :
        dict[word[0]] = []
        dict[word[0]].append(word)
ans = []
a = ''
while len(sentence) != 0:
    if sentence[0] in dict:
        prob = []
        for j in dict[sentence[0]]:
            if j in sentence[:len(j)]:
                prob.append(j)
        sure = ''
        if len(prob) != 0:
            if len(a) != 0:
                ans.append(a)
            for i in prob:
                if len(i) >= len(sure):
                        sure = i
            ans.append(sure)
            a = ''
        else:
            a += sentence[0]
            sentence = ''+sentence[1:]
        sentence = sentence[len(sure):]
        prob = []
        sure = ''
    else:
        a += sentence[0]
        sentence = ''+sentence[1:]
        if len(sentence) == 0:
            ans.append(a)
ans1 = []
for i in ans:
    if i != '':
        ans1.append(i)
correct = ' '.join(ans1)
print(correct)

# 6331320421 1295622 (2020-12-04 16:13)
s = input()
dic = dict()
n = int(input())
for i in range(n) :
    x = input()
    if x[0] not in dic :
        dic[x[0]] = set()
    dic[x[0]].add(x)
s = s.lower()
t = list()
a = ''
while True :
    match = False
    if s[0] in dic :
        for i in range(len(s),0,-1) :
            if s[:i] in dic[s[0]] :
                if len(a) != 0 :
                    t.append(a)
                    a = ''
                t.append(s[:i])
                s = s[i:]
                match = True
                break
        if not match :
            a += s[0]
            s =s[1:]
    else :
        a += s[0]
        s = s[1:]
    if len(s) == 0 : 
        if len(a) != 0 :
            t.append(a)
        break
if len(t) != 0 :
    print(' '.join(t))
else :
    print(a)

# 6331321021 1295768 (2020-12-04 19:29)
text = input().lower().strip()
n = int(input())
dic = []
ans = []

for i in range(n) :
    m = input()
    dic.append(m)

c = 0
an = ""

while len(text) != 0 :
    for s in range(len(text)) :
        for i in range(len(text),s,-1) :
            to_out = False
            if len(text[s:i]) == 1 :
                an += text[s:i]
                text = text[1:]
                to_out = True ;break
            
            elif text[s:i] in dic :
                if an != '':
                    ans.append(an)
                    an = ""
                ans.append(text[s:i])
                text = text[i:]
                to_out = True ;break
        if to_out : break
if an != "" :
    ans.append(an)
print(" ".join(ans))


# 6331322721 1295996 (2020-12-04 22:42)
wordInput = input().lower()
nDict = int(input())
dictList = []
wordList = []
wordOutput = ''
for i in range(nDict) :
    dictWord = input().lower()
    dictList.append(dictWord)
i = 0
while len(wordInput) > 0 :
    if wordInput[:len(wordInput)-i:] in dictList :
        wordList.append(wordInput[:len(wordInput)-i:])
        wordInput = wordInput[len(wordInput)-i::]
        i = 0
    elif len(wordInput[:len(wordInput)-i:]) == 1 :
        wordList.append(wordInput[:len(wordInput)-i:])
        wordInput = wordInput[len(wordInput)-i::]
        i = 0
    else :
        i += 1
for a in range(len(wordList)):
    i=wordList[a]
    if i not in dictList :
        if a != 0 :
            if wordList[a-1] not in dictList :
                wordOutput += i
            elif wordList[a-1] in dictList :
                wordOutput += ' ' + i
        else :
            wordOutput += i
    else :
        if wordList.index(i) != 0 :
            wordOutput += ' ' + i
        else :
            wordOutput += i
print(wordOutput)

# 6331323321 1295616 (2020-12-04 16:06)
# 6331323321 ทำด้วยตัวเอง แน่นอน!

s = input().strip().lower()
n = int(input())
result = []

# สร้าง word dictionary เป็นลิสต์เก็บข้อมูลนำเข้า
# แล้ว sort ตามความยาวของแต่ละ element
d = [input().strip().lower() for i in range(n)]
d = sorted(d,key=len,reverse=True)

c = 0
while s != '':
    c += 1
    to_break = False
    # สร้างลิสต์เก็บสตริงทั้งหมดที่ได้จากการ slice หาง (ยกเว้นสตริงเปล่า)
    # แล้ว sort ตามความยาวของแต่ละ element
    a = [s[:i+1] for i in range(len(s)) if s[:i+1]!='']
    a = sorted(a,key=len,reverse=True)
    # สำหรับสตริงทั้งหมดจากการ slice ไล่หาดูใน dictionary
    # ถ้าพบสตริงนั้นใน dictionary ให้เก็บไว้ในลิสต์อีกตัว
    # แล้ว sort ตามความยาวของแต่ละ element
    choose = [e1 for e1 in a if e1 in d]
    choose = sorted(choose,key=len,reverse=True)
    # หากเจอคำใน dictionary
    try:
        # ใช้คำแรกในลิสต์ choose (เพราะเป็น longest matching)
        # เพิ่มคำนั้นลงไปใน result แล้วตัดออกจากข้อมูลนำเข้าตอนแรก
        result.append(choose[0])
        s = s.replace(choose[0],'',1)
    # หากไม่เจอคำใน dictionary
    except:
        to_break = False
        # ไล่หาสตริงทั้งหมดที่ได้จากการ slice หัวและหาง
        for i in range(len(s)):
            for j in range(i+1,len(s)):
                e2 = s[i:j+1]
                # เมื่อพบสตริงจากการ slice ใน dictionary
                if e2 in d:
                    # ใช้สตริงก่อนหน้า (ที่ไม่พบใน dictionary)
                    # เพิ่มคำนั้นลงไปใน result แล้วตัดออกจากข้อมูลนำเข้าตอนแรก
                    result.append(s[:i])
                    s = s.replace(s[:i],'',1)
                    to_break = True
                    break
            if to_break:
                break
        # ถ้าพบสตริงจากการ slice ใน dictionary ก็วนลูปต่อไป
        if to_break:
            continue
        # ถ้าไม่พบสตริงจากการ slice ใน dictionary แสดงว่าแยกประโยคไม่ได้แล้ว
        result.append(s)
        s = ''
    
print(' '.join(result))

# 6331324021 1295649 (2020-12-04 17:12)
message = input().lower()
N = int(input())
dtnr = []
for i in range(N):
    dtnr.append(input())
dtnr.sort()
dtnr.sort(key=lambda r:-len(r))

message = "  " + message + "  "

for word in dtnr:
    index = message.find(word)
    while index != -1 and (message[index-1]!="[" or message[index+len(word)] != "]"):
        if message[index-1]!="[" and message[index+len(word)] != "]":
            message = message[:index] + "[" + message[index:]
            index = message.find(word,index)
            message = message[:index+len(word)] + "]" + message[index+len(word):]
        index = message.find(word,index+1)

message = message.strip()

count = 0
ans = ""
for c in message:
    if c == "[":
        if count == 0:
            ans += " "
        count += 1
    elif c== "]":
        count -= 1
        if count == 0:
            ans += " "
    else:
        ans += c

ans = ans.replace("  "," ")
ans = ans.strip()
print(ans)

# 6331325621 1287897 (2020-11-17 09:48)
word=input().strip()
wl=[]
out=[]
pastword=''
for i in range(int(input())):
    wl.append(input().strip())
while word:
    outword=''
    for i in range(1,len(word)+1):
        if word[0:i].lower() in wl:outword = word[0:i].lower()
    if outword:
        pass
    else:pastword+=word[0]
    if outword:
        if pastword:
            out.append(pastword.lower())
            pastword=''
        out.append(outword.lower())       
    if outword:word=word[len(outword):]
    else :word=word[1:]
if pastword:out.append(pastword.lower())
print(' '.join(out).strip())

# 6331326221 1295644 (2020-12-04 16:48)
word = input()
n = int(input())
dic = []
word2 = [word]
for i in range(n):
    a = input()
    dic.append(a)
words = []
while len(word)!=0:
    wordd = ''
    aw = False
    for k in word:
        wordd += k
        if wordd in dic:
            wordaw = wordd
            aw = True
    if aw == False:
        word = word[1:]
    else:
        words.append(wordaw)
        word = word[len(wordaw):]
if words==[]:
    print(word2[0])
else:
    wordfinal = []
    #for u in range(len(word2[0])):
    for uu in words:
        if word2[0][:len(uu)]==uu:
            wordfinal.append(uu)
            word2[0] = word2[0][len(uu):]
        else:
            for kk in range(len(word2[0])-len(uu)+1):
                if word2[0][kk:kk+len(uu)]==uu:
                    aww = word2[0][:kk]
                    wordfinal.append(aww)
                    wordfinal.append(uu)
                    word2[0] = word2[0][len(aww)+len(uu):]
                    break
    print(' '.join(wordfinal))

            

        


# 6331327921 1295668 (2020-12-04 18:19)
w = ''
st = ''
words = ''
cut = []
dic = []
word = input()
n = int(input())
for i in range(n) :
    d = input()
    dic.append(d)
c = 0
while len(word) != 0 :
    w += word[c]
    if w in dic :
        words = w
    if word in dic :
        cut.append(' ')
        cut.append(word)
        cut.append(' ')
        break
    else :
        if w == word and len(words)==0:
            cut.append(word[0])
            word = word[1:]
            c = -1
            w = ''
            words = ''
        elif w == word and len(words)!=0:
            cut.append(' ')
            cut.append(words)
            cut.append(' ')
            word = word[len(words):]
            c = -1
            w = ''
            words = ''
    c += 1
final = ''.join(cut).strip()
print(final.replace('  ',' '))

# 6331328521 1296092 (2020-12-05 01:21)
a = input().lower()
g = a
b = int(input())
dict1 = []
for i in range(b):
    dict1.append(input())
j = []
for i in dict1:
    j.append(len(i))
str_cut = []
if j != []:
  for i in range(max(j),0,-1):
    for start in range(len(a)):
        max_word = a[start:start+i]
        if max_word in dict1:
            str_cut.append([start,start+i])
            a = a[:start]+"1"*i+a[start+i:]
Ans = ""
list2 = []
for i in str_cut:
    for j in i:
        list2.append(j)
Answer = ""
for i in range(len(g)):
    if i in list2:
        Answer += " " +g[i]
    else:
        Answer += g[i]
print(Answer)

# 6331329121 1295654 (2020-12-04 17:19)
text = input().strip()

n = int(input())

book = []

for i in range(n):
    book.append(input().strip())

ans = []
notinbook = ''

while len(text) != 0:
    check = False
    wordlist = []
    for i in book:
        if i in text:
            if text.index(i) == 0:
                wordlist.append(i)
                check = True
    if check == False:
        notinbook += text[0]
        text = text[1:]
    else:
        maxlen = 0
        word = ''
        for i in wordlist:
            if len(i) > maxlen:
                maxlen = len(i)
                word = i
        if notinbook != '':
            ans.append(notinbook)
        ans.append(word)
        text = text[len(word):]
        notinbook = ''
if notinbook != '':
    ans.append(notinbook)

print(' '.join(i for i in ans))       

# 6331330721 1296148 (2020-12-05 11:29)
s = input().strip()
n = int(input())
dic = set()
for i in range(n):
    dic.add(input().strip())

out = ''
m = False
while len(s) != 0:
    match = []
    for i in range(1,len(s)+1):
        if s[:i] in dic:
            match.append(s[:i])
    if len(match) != 0:
        if not m:
            out += ' '
        m = True
        out += match[-1] + ' '
        s = s[len(match[-1]):]
    else:
        m = False
        out += s[0]
        s = s[1:]

print(out.strip())

# 6331331321 1295673 (2020-12-04 18:21)
str=input().lower().strip()
n=int(input())
dict=[]
ans=''
b=True
a=True
check=False
le=0
for i in range(n):
    c=input().strip()
    dict.append(c)
while a==True:
    j=len(str)
    b=True
    while b==True:
        pro=str[le:j]
        #print(pro)
        if pro in dict:
            if check == True:
                ans+=' '
            ans+=pro
            #print(le)
            ans+=' '
            check=False
            #if le<len(str):
                
            b=False
            le+=len(pro)
            #print(le)
            #print(len(str))
            #else:
                #print(ans)
                #b=False
                #a=False
                
        else:
            if le<len(str) and j>le+1:
                j-=1
            elif le==len(str)-1:
                ans+=pro
                #print(le)
                le+=1
                check=True
                b=False
                a=False
            elif le==len(str):
                b=False
                a=False
            else:
                ans+=pro
                le+=1
                check=True
                b=False
print(ans)


# 6331332021 1295643 (2020-12-04 16:40)
# while len(newword) != 0
# 1)if len(newword) == 1:
#     if len(s) != 0: --> s+= newword
#     else: --> s = newword
#      out.append(s)
#      break      
# 2) เช็ค alphaอยู่ใน dicไหม
#  - ถ้าไม่อยู่เพิ่ม alphaใน s --> เปลี่่ยน newword
#  - ถ้าอยู่ก็เอา sที่เก็บได้ไปappendใน out --> s='' --> เช็คในdic -->
# appendในout -->เปลี่่ยน newword --> break
# ------------------------------------------------------
word = input().lower()
temp = []
n = int(input())
for i in range(n):
    x = input()
    temp.append([len(x),x])
dic = []
for i in sorted(temp)[::-1]:
    dic.append(i[1])

newword = word
s = ''
out = []
while len(newword) != 0:
    if len(newword) == 1:
        if len(s) != 0:
            s += newword
        else:
            s = newword
        out.append(s)
        break
    
    found = False
    for e in dic:
        if newword.find(e) == 0:
            if len(s) != 0:
                out.append(s)
                s = ''
            out.append(e)
            newword = newword[len(e):]
            found = True
            break
    if not found:
        s += newword[0]
        newword = newword[1:]
print(' '.join(out))

# 6331333621 1295722 (2020-12-04 18:52)
x=input().lower()
n=int(input())
b=[]
y=0
k=0
running=True
word=[]
ans=[]
diao=""
for i in range(n):
    a=input()
    b.append(a)
while running:
    k+=1
    if x[y:y+k] in b:
        word.append((len(x[y:y+k]),x[y:y+k]))

        
    if y+k==len(x)+1:
        if len(word)>0:
            word.sort(reverse=True)
            if diao!="":
                ans.append(diao)
                diao=""
            ans.append(word[0][1])
            y=y+word[0][0]
            k=0
            word=[]
        else:
            diao+=x[y]
            #ans.append(x[y])
            y=y+1
            k=0
    
    if y==len(x):
        if diao!="":
            ans.append(diao)
        break
print(" ".join(ans))

# 6331334221 1296012 (2020-12-04 23:06)
s=input()
s=s.lower()
n=int(input())
dic=[]
for y in range(n):
    e=input()
    e=e.lower()
    dic.append(e)
ans=''
while s!='':
    i=1
    maxx=1
    found=False
    while i <= len(s):
        if s[:i] in dic :
            maxx=i
            found=True
        i+=1
    if found :
        ans+=' '
    ans+=s[:maxx]
    if found :
        ans+=' '
    s=s[maxx:]
print(ans.strip())

# 6331337121 1296290 (2020-12-05 20:32)
text = input().lower()
n = int(input())
words = []
for i in range(n):
    words.append(input())
copy = text
data = []
i = 0
while copy != '':
    most = 0
    for word in words:
        index = copy.find(word)
        if index != -1:
            if most < len(word):
                most = len(word)
                most_index = index
                most_word = word
    if most != 0:
        data.append((copy.find(most_word), most_word))
        copy = copy[:most_index]+' '*most+copy[most_index+most:]
    else:
        break
prev = 0
out = ''
data.sort()
for index, word in data:
    if text[prev:index] != '':
        out += text[prev:index]+' '
    out += word+' '
    prev = index+len(word)
out += text[prev:]
print(out.strip())


# 6331338821 1296220 (2020-12-05 16:03)
text = input().lower()
n = int(input())
e = []
ch = ""
for i in range(n):
    vocab = input()
    e.append((vocab,len(vocab)))
es = sorted(e, key=lambda l: l[1])

while len(text)>0:
    a = len(text)
    new=""
    for x in es:
        try:
            if text.index(x[0]) <= a:
                a = text.index(x[0])
                new = x[0]
        except ValueError:
            continue
    if len(new) > 0:
        ch += text[0:a]+" "+text[a:a+len(new)]+" "
        text = text[a+len(new)::]
    else:
        ch += text
        text = ""
print(" ".join(ch.strip().split()))

# 6331340021 1295657 (2020-12-04 17:43)
txt = input()
txt = txt.lower()
n = int(input())
dictionary = []
initial = []
res = []
txt2 = ""
i = 0
for k in range(n):
    word = input()
    dictionary.append(word)
newdict = sorted(dictionary, key = len, reverse = True)
for d in range(len(newdict)):
    if newdict[d][0] not in initial:
        initial.append(newdict[d][0])
while i < (len(txt)):
    if txt[i] not in initial:
        txt2 += txt[i]
        i += 1
    else:
        for d in range(len(newdict)):
            if newdict[d] == txt[i:i+len(newdict[d])]:
                if txt2 != "":
                    res.append(txt2)
                    txt2 = ""
                res.append(txt[i:i+len(newdict[d])].strip())
                i += len(newdict[d])
                break
        else:
            if i != len(txt):
                txt2 += txt[i]
                i += 1
if txt2 != "":
    res.append(txt2)
print(" ".join(res).strip())


# 6331341621 1296440 (2020-12-06 21:03)
word = input().strip().lower()
split_word = []
for i in range(int(input().strip())):
    split_word.append(input().strip())

 #ตัวที่ยาวที่สุด
op = []
keep = ''
while word!='':
    one_alphabet = True
    word_check = ''
    e = ''
    for i in range(len(word)):
        word_check += word[i]
        if word_check in split_word and len(word_check)>len(e):
            e = word_check
            one_alphabet = False

    if one_alphabet:
        keep += word[0]
        word = word[1:]
    else:
        op.append(keep)
        op.append(e)
        keep = ''
        word = word[len(e):]
op.append(keep)
oup = []
for e in op:
    if e!='':
        oup.append(e)
print(' '.join(oup))

# 6331342221 1287873 (2020-11-17 09:40)
s = input().strip().lower()
n = int(input())
words = set()
for i in range(n):
    words.add(input().strip().lower())

cs = 0
sp = []
last_found = True
while cs < len(s):
    candidate = s[cs]
    this_found = False
    for ce in range(cs, len(s)+1):
        
        if s[cs:ce] in words:
            candidate = s[cs:ce]
            this_found = True
    if this_found:
        sp.append(candidate)
        last_found = True
    elif last_found:
        sp.append(candidate)
        last_found = False
    else:
        sp[-1] += candidate
        last_found = False
    cs += len(candidate)
            
print(' '.join(sp))


# 6331343921 1287901 (2020-11-17 09:50)
s = input().strip().lower()
n = int(input())
voc = [input().strip().lower() for i in range(n)]
sen = []
while s != '':
    for i in range(len(s),0,-1):
        x = s[0:i:]
        if x in voc:
            sen.append(x)
            ischar = False
            s = s[i::]
            break
        elif len(x) == 1:
            if len(sen) == 0:
                sen.append(x)
            elif ischar:
                sen[-1] += x
            else:
                sen.append(x)
            s = s[i::]
            ischar = True
print(' '.join(sen))

# 6331344521 1287898 (2020-11-17 09:49)
code = input().strip().lower()
dct = dict()
for i in range(int(input())) :
    s = input().strip().lower()
    dct[s] = True
new_sen = ''
i = 0
j = 0
last_word = True
while i < len(code) :
    j = i
    word = ""
    mx = 0
    wordmx = ''
    wordj = -1
    while j < len(code) :
        word += code[j]
        if word in dct and len(word) > mx:
            mx = len(word)
            wordmx = word
            wordj = j
        if j == len(code)-1 and not mx:
            last_word = False
            new_sen += code[i]
            #print(mx)
        if j == len(code)-1 and mx :
            if last_word == False :
                new_sen += ' '
            new_sen += wordmx + ' '
            last_word = True
            i = wordj
        j += 1
    #print(word)
    i += 1
print(new_sen.strip())


# 6331345121 1295869 (2020-12-04 21:07)
s = input().strip()
n = int(input())

s = s.lower()

words= []
for _ in range(n):
    x = input().strip()
    x = x.lower()
    words.append((x, len(x)))
    
words = sorted(words)
words = sorted(words, reverse=True, key=lambda x: x[1])
# print(words)

for word, l in words:
    idx = 0
    while True:
        if idx >= len(s): break
        if s[idx]=='|':
            idx += 1
            while idx < len(s) and s[idx]!='|':
                idx += 1
        if(s[idx: idx+l] == word):
            s = s[:idx]+'|'+s[idx: idx+l]+'|'+s[idx+l:]
            idx += l+1
        idx += 1

ans = s.split('|')
print(' '.join([e for e in ans if e != '']))


# 6331346821 1296613 (2020-12-09 13:08)
sentence = input()
len_dict = int(input())
dict_word = []
new_s = ""
word_add = ""
def clear():
  word =""

for i in range(len_dict):
  dict_word.append(input())
i = 0

while i < len(sentence):
  word_add =""
  for y in range(len(sentence)-i+1):
    if sentence[i:i+y] in dict_word:
      word_add = sentence[i:i+y]
    else:pass
  if word_add == "": 
    new_s += " " + sentence[i] + " "
    i += 1
  else: 
    new_s += " " + word_add + " "
    i += len(word_add)
    word_add =""
if word_add == "": 
    pass
else: 
    new_s += " " + word_add
e = new_s.split()
new_ss = ""
for x in e:
  if x in dict_word:
    new_ss += " " + x + " "
  else: new_ss += x
  
new_sss = new_ss.split()

new_ssss= new_sss[0]

for j in range(1,len(new_sss)):
  new_ssss += " " + new_sss[j]
print(new_ssss)

# 6331347421 1288044 (2020-11-17 10:25)
def findWord(text) :
    same=text[0]
    for i in range(1,len(text)) :
        for word in wordList :
               if same in word :
                    same+=text[i]
                    break
    if len(same) == len(text) :
        return same
    if same[:-1] in wordList :
        return same[:-1]
    return same[:-2]
    
wordList=[];result=''
text = input().lower().strip()
n = int(input())
for i in range(n): #input dictionary
    wordList.append(input())
while len(text) > 0 :
    word = findWord(text)
    #print(text,word)
    if word in wordList : 
        result = result.strip()+" "+word+" "
        text=text[len(word):]
    else :
        if len(word) >0 :
            result+=word
            text=text[len(word):]
        else :
            result+=text[0]
            text=text[1:]
        
print(result.strip())

# 6331348021 1296693 (2020-12-09 23:39)
a = input()
n = int(input())
dic = []
for i in range(n):
    b = input()
    dic += [b]
word = ''
vocab = set()
lenvocab = []
for i in range(len(a)):
    word += a[i]
    for j in range(len(dic)):
        if dic[j] in word:
            vocab.add(dic[j])
vocab = list(vocab)
vocab1 = []
for i in range(len(vocab)):
    lenvocab.append([-1*len(vocab[i]), vocab[i]])
lenvocab.sort()
for i in range(len(lenvocab)):
    vocab1.append(lenvocab[i][1])
vocab2 = {}
for i in range(len(vocab1)):
    if vocab1[i][0] not in vocab2:
        vocab2[vocab1[i][0]] = [vocab1[i]]
    else:
        vocab2[vocab1[i][0]].append(vocab1[i])
ans = []
a1 = ''
i = 0
while len(a) != 0:
    d = True
    c = False
    for e in vocab2:
        c = True
        if len(a) != 0:
            if e == a[0]:
                for h in vocab2[e]:
                    if h == a[:len(h)]:
                        ans.append(a1)
                        ans.append(h)
                        a = a[len(h):]
                        a1 = ''
                        d = False
                        c = True
                        break
                    else:
                        c = False
            else:
                c = False
        if d == False:
            break
    if c == False:
        if len(a) != 0:
            a1 += a[0]
            a = a[1:]
            i += 1
ans.append(a1)
ans1 = []
for i in range(len(ans)):
    if ans[i] != '':
        ans1.append(ans[i])
print(' '.join(ans1).strip())

# 6331349721 1296418 (2020-12-06 19:46)
p=input().lower()
n=int(input())
dictionary=dict()
ans=''
for i in range(n):
    k=input()
    dictionary[k]=len(k)
st=0
m_ed=0
space=False
space2=False
while True :
    m=p[st:]
    if len(ans)!=0:
        if ans[-1]!=' ' and space2==True :
           ans+=' '
           space2=False
    if len(m)==0 :
        break
    for key in dictionary:
        if m[0]==key[0] and len(m)>=len(key):
            for i in range(len(key)):
                if m[i]==key[i]:
                    if i==len(key)-1:
                        if m_ed <= i :
                           m_ed=i+1
                           space=True
                           space2=True



                else:
                    break
            
    if space and len(ans)!=0 and ans[-1]!=' ':
        ans+=' '
        space=False
    else:
        space=False
    if m_ed==0:
        k=m[0]
        st+=1
    if m_ed>0 :
        k=m[:m_ed]
        st+=m_ed
        m_ed=0
    
    
    ans+=k
    
print(ans)

# 6332001421 1288002 (2020-11-17 10:14)
a=input()
n=int(input())
c=[]
for i in range(n):
    b=input()
    c.append((-len(b),b))
c.sort()
before=False
i=0
ans=''
while i< len(a):
    lengh=0
    for vv,word in c:
        if -vv <= len(a)-i and word==a[i:i+(-vv)]:
            lengh=-vv
            break
    if lengh:
        ans+=' '
        ans+=a[i:i+lengh]
        before=True
        i+=lengh
    elif before==True:
        ans+=' '
        ans+=a[i]
        before=False
        i+=1
    else :
        ans+=a[i]
        before=False
        i+=1
print(ans)


# 6332002021 1288574 (2020-11-17 11:24)
def main() :
    pat = dict()
    txt = input().strip()
    n = int(input())
    for i in range(n):
        t = input().strip()
        pat[t] = True
    sz = len(txt)
    s = 0
    prev = ''
    while s < sz :
        point = ('',s+1)
        found = False
        for i in range(s,sz+1) :
            if txt[s:i].lower() in pat :
                point = (txt[s:i],i)
                found = True
        if  not found :
            prev += txt[s]
            s += 1
        else :   
            s = point[1]
            if prev != '' :
                print(prev.lower(),end=' ')
            print(point[0].lower(),end = ' ')
            prev = ''
    if prev != '' :
        print(prev.lower(),end=' ')
        

main()


# 6332003721 1288476 (2020-11-17 11:17)
rawtxt = input()
n = int(input())
tmpdict = [] 
for lo in range(n) :
    x = input()
    tmpdict.append(x)

i = 0
ans = ''
bfw = True
while i < len(rawtxt) :
    Max=0
    txt =''
    #print(rawtxt[i:i+3])
    for d in tmpdict :
        if i+len(d)<=len(rawtxt) and rawtxt[i:i+len(d)] == d :
            if Max < len(d) :
                Max= len(d)
                txt = d
    if Max!=0 :
        if not bfw :
            ans += ' '
        ans+=txt+' '
        bfw = True
        i+=Max
        Max=0
    else :
        ans+=rawtxt[i]
        bfw = False
        i+=1
    #print(i)

print(ans.strip())
    
    


# 6332004321 1295911 (2020-12-04 21:37)
text = input().strip().lower()
original = text
n = int(input().strip())
dic = []
found = []
for _ in range(n):
    word = input().strip()
    dic.append((-len(word), word))

dic = sorted(dic)
dic = [(-a, b) for (a, b) in dic]

for (wl, word) in dic:
    end = False
    while not end:
        idx = text.find(word)

        if idx == -1:
            end = True
            continue
        
        found.append((idx, word))
        text = text[:idx] + ("@" * wl) + text[idx+wl:]

found = sorted(found)
result = []
cur = 0
for (start, word) in found:
    t = original[cur:start]
    if len(t) > 0:
        result.append(t)
    result.append(word)
    cur += len(word) + len(t) 

t = original[cur:]
if len(t) > 0:
    result.append(t)

print(" ".join(result))

# 6332006621 1287905 (2020-11-17 09:51)
str = input().lower()
num = int(input())
dict = []
found = True
answer = ''
for i in range(num):
    dict.append(input())

i = 0
while i < len(str):
    max = 0
    for j in range(i,len(str)):
        if str[i:j+1] in dict:
            max = j
    if max != 0:
        if found == False:
            answer += ' '
        answer += str[i:max+1] + ' '
        i = max + 1
        found = True
    else:
        answer += str[i]
        i += 1
        found = False
print(answer)
    

# 6332008921 1287888 (2020-11-17 09:46)
a = input()
n = int(input())
d = dict()
for i in range(n):
    word = input()
    d[word] = 1;
ans = []
i = 0
tmp2 = ''
while(i<len(a)):
    word = ''
    tmp = ''
    for j in range(i,len(a)):
        word += a[j]
        if word in d:
            tmp = word
            i = j+1
    if tmp == '':
        tmp2 += a[i]
        i += 1
    else:
        if tmp2 != '':
            ans.append(tmp2)
            tmp2 = ''
        ans.append(tmp)
        tmp = ''
if tmp != '':
    ans.append(tmp)
if tmp2 != '':
    ans.append(tmp2)
print(' '.join(ans))


# 6332009521 1295705 (2020-12-04 18:40)
m = input().strip().lower()
n = int(input())
first_dic = [input().strip() for i in range(n)]
dic = sorted([(-len(c), c) for c in first_dic])
out = ''
while m != '':
    list_index = [m.find(c) for i, c in dic if m.find(c) != -1]
    if list_index == []:
        out += m+' '
        m = ''
    else:
        mn = min(list_index)
        if mn != 0:
            out += m[:mn]+' '
            m = m[mn:]
        for i, c in dic:
            if m.find(c) == 0:
                out += c+' '
                m = m[len(c):]
                break
print(out[:-1])

# 6332011721 1287880 (2020-11-17 09:43)
text=input()
a = int(input())
dict = list()
newtext = ""
ans = list()
for i in range(a):
    ins = input()
    dict.append(ins)
for i in range(len(text)):
    newtext+=text[i].lower()
i=0
addon = ""
while i <len(newtext):
    start=i
    stop=i-1
    for j in range(i,len(newtext)+1):
        check=newtext[i:j]
        if(check in dict):
            stop=j
    if(stop!=i-1):
        if(addon!=""):
            ans.append(addon)
            addon=""
        ans.append(newtext[i:stop])
        i=stop
    else:
        addon+=newtext[i]
        i+=1
if(addon!=""):
    ans.append(addon)
    addon=""
print(" ".join(ans))


        


# 6332014621 1287907 (2020-11-17 09:51)
inp = input().lower()
n = len(inp)
status = [0]*len(inp) # 2 and more for word, 1 for not word,0 for nothing
cnt = 2
m = int(input())
dictS = set()
for i in range(m) :
    word = input().lower()
    dictS.add(word)
    
i = 0
while i < n :
    max_len = 0
    for j in range(i,n) :
        if inp[i:j+1] in dictS :
            max_len = len(inp[i:j+1])
            #print(inp[i:j+1])
            
    if max_len > 0 :
       # print(max_len)
        for j in range(i,i+max_len) :
            status[j] = cnt
        i += max_len
        cnt += 1
    else :
        status[i] = 1
        i += 1
        
#print(status)

ans = []
i = 0
while i < n :
    j = i
    while j < n and status[i] == status[j]:
        j += 1
    ans.append(inp[i:j])
    i = j
    
#print(ans)
print(ans[0],end="")
for i in range(1,len(ans)) :
    print(" "+ans[i],end="")
        
    


# 6332015221 1288024 (2020-11-17 10:19)

def n_sort(x):
    for i in range(len(x)):
        for j in range(len(x)):
            if len(x[i])>len(x[j]):
                x[i],x[j] = x[j],x[i]
    return x

s = input()

n = int(input())

m = []

for e in range(n):
    m.append(input())

m = n_sort(m)

ans = ""

q = len(s)

some = 0

for e in range(q):
    if some==0:
        c = False
        for p in m:
            if s[e:e+len(p)] == p:
                ans+= " "+p+" "
                some+=len(p)-1
                c = True
                break
    else:
        some-=1
    if not c:
        ans += s[e]
print(ans)

# 6332016921 1288154 (2020-11-17 10:47)
inp = input()
leninp = len(inp)
N = int(input())
dict_ = dict()
for i in range(N):
    x = input()
    dict_[x] = len(x)
sort = sorted(dict_.items(),key = lambda x:(-x[1],x[0]))
found = False
start = -1
while(True):
    start += 1
    for j in range(len(sort)):
        for i in range(start,leninp):
            if(sort[j][0]==inp[start:i+1]):
                print(" {} ".format(sort[j][0]),end='')
                found = True
                tmp = sort[j][1]
                break
        if(found):
            start += tmp -1
            break
    if(start==leninp):
        break
    if(not found):
        print(inp[start],end='')
        found = False
    found = False
    



# 6332018121 1288177 (2020-11-17 10:50)
word=str(input())
num_dict=int(input())
dict=[]
for i in range(num_dict):
    k= str(input())
    dict.append(k)
    

dict_sort=sorted(dict, key=lambda dic:len(dic), reverse=True)


word_check=word.lower()
new=''
while len(word_check)!=0:
    #for i in range(len(word_check)):
    if len(dict_sort)==0:
        new=new+word_check
        break
    for i in range(len(dict_sort)):
        if dict_sort[i]==word_check[:len(dict_sort[i])]:

            word_check=word_check.replace(dict_sort[i],'',1)
            #if len(word_check)!=0:
            try:
                if new[-1]!=' ':
                    new=new+' '
            except:
                pass
            new=new+dict_sort[i]
            if len(word_check)!=0:
                new=new+' '
            break
        if i==len(dict_sort)-1:
            new=new+word_check[0]
            word_check=word_check.replace(word_check[0],'',1)

        
print(new)
    
    






#for step in range(len(word)):
    


# 6332019821 1287984 (2020-11-17 10:09)
s = input().lower()
sa = s
ans = ''
n = int(input())
dic = set()
word = False
for i in range(n):
  w = input().strip()
  dic.add(w)
i = 0
while i < len(sa):
  inx = -1
  for j in range(i,len(sa)):
    w = sa[i:j+1]
    if w in dic:
      ma = w
      inx = j
  if inx != -1:
    ans += ' ' + sa[i:inx+1]
    i=inx
    word = True
  else:
    if word:
        ans+=' '
        word = False
    ans += sa[i]
  i+=1
print(ans.strip())
    
'''
Thisisadog
8
these
this
is
a
and
his
sad
dog
'''



# 6332020321 1288008 (2020-11-17 10:16)
a = input()
n = int(input())
d = []
for i in range(n):
    temp = input()
    d.append(temp)

temp = ""
c = len(a)
ans = []
while a != "":
    if a[:c] in d :
        if temp != "":
            ans.append(temp)
            temp = ""
        ans.append(a[:c])
        a = a[c:len(a)]
        c = len(a)
    else :
        if c!= 0:
            c -= 1
        else:
            temp += a[0]
            a = a[1:len(a)]
            c = len(a)
if temp != "":
    ans.append(temp)
            
print(" ".join(ans))


# 6332022621 1288259 (2020-11-17 11:00)
s = input().lower()
n = int (input())
dct = [input() for i in range(n)]
ans = []
i = 0
word = ''
while i<len(s):
    mx = -1
    for e in dct:
        if i+len(e)<=len(s):
            if s[i:i+len(e)]==e:
                mx = max(mx,len(e))
    if mx==-1:
        word+=s[i]
        i+=1
    else:
        if word!='':
            ans.append(word)
        ans.append(s[i:i+mx])
        word = ''
        i+=mx
if word!='':
    ans.append(word)
print(' '.join(ans))


# 6332024921 1287917 (2020-11-17 09:53)
s = input()
n = int(input())
d = dict()
l = len(s)
ans = ""
for i in range(n):
    c = input()
    d[c] = 1
now = 0
count = 0
while now != l:
    t  = -1
    count += 1
    #print(now)
    if count > 1000000: break
    for j in range(now,l+1):
        #print(s[now:j])
        if s[now:j] in d:
            t = j
    if t != -1:
        ans += " "+s[now:t]+" "
        now = t
    else:
        ans += s[now]
        now += 1
    #print("x "+ans)
print(ans)


# 6332027821 1287914 (2020-11-17 09:52)
a = input()
n = int(input())
dic = set()
ans = []
chk = [False for i in range(len(a))]
for i in range(n):
    tmp = input()
    dic.add(tmp)
for i in range(len(a),0,-1):
    for j in range(0,len(a)-i+1):
        if chk[j] or chk[j+i-1]:
            continue
        if a[j:j+i] in dic:
            ans.append((j,a[j:j+i]))
            for k in range(j,j+i):
                chk[k] = True
tmp = ''
start = 0
for i in range(len(a)):
    if not chk[i]:
        tmp += a[i]
    else:
        if len(tmp):
            ans.append((start,tmp))
            tmp = ''
        start = i+1
if len(tmp):
    ans.append((start,tmp))
ans.sort()
ou = ''
for i in range(len(ans)):
    ou += ans[i][1]
    if i < len(ans)-1:
        ou += ' '
print(ou)


# 6332028421 1287875 (2020-11-17 09:40)
data=input().lower()
n=int(input())
wordList=set()
for i in range(n):
    word=input().lower()
    wordList.add(word)
output=""
lastMode=False
i=0
while i<len(data):
    lastPos=-1
    for j in range(i,len(data)):
        if data[i:j+1] in wordList:
            lastPos=j
    if lastPos==-1:
        if lastMode:
            output+=data[i]
        else:
            lastMode=True
            output+=" "+data[i]
    else:
        if lastMode:
            lastMode=False
        output+=" "+data[i:lastPos+1]
        i=lastPos
    i+=1
print(output.strip())


# 6332029021 1287902 (2020-11-17 09:50)
d = dict()
ip = input()
#oip = ip
ip = ip.lower()
n = int(input())
cd = None
for i in 'qwertyuiopasdfghjklzxcvbnm':
    d[i] = dict()
    d[i]['END'] = False
for i in range(n):
    cd = d
    k = input().strip()
    for i in k:
        if i not in cd:
            cd[i] = dict()
        cd = cd[i]
    cd['END'] = True
#print(d)

i = 0
lv = 0
#cs = ''
ans = []
sp = ''
while i<len(ip):
    #print(">>",i)
    j = i
    cd=d
    while ip[j] in cd:
        #print(">",j)
        if 'END' in cd[ip[j]]:
            lv = j
            s = cd[ip[j]]['END']
        cd = cd[ip[j]]
        j +=1
        if j>=len(ip):
            break
    if s:
        if len(ans) > 0:
            if ans[-1][-1] == ' ':
                sp = ''
            else:
                sp = ' '
        ans.append(sp+ip[i:lv+1]+' ')
    else:
        ans.append(ip[i:lv+1])
    #print(oip[i:lv+1])
    i = lv+1
print(''.join(ans))
        


# 6332031221 1288419 (2020-11-17 11:13)
s = input()
n = int(input())
dict = []
s = s.lower()
for i in range(n):
    dict.append(input())
def cut(s,st):
    ans = -1
    for x in dict:
        ch = 0
        for j in range(len(x)):
            if st+j>=len(s):
                ch=1
                break
            if s[st+j]!=x[j]:
                ch=1
                break
        if ch==0:
            ans = max(ans,st+len(x))
    return ans
tmp = ""
i=0
while i<len(s):
    x = cut(s,i)
    if x!=-1:
        if tmp!= '':
            print(tmp,end=' ')
            tmp=''
        print(s[i:x],end = ' ')
        i=x
    else:
        tmp+=s[i]
        i+=1
if tmp!= '':
    print(tmp,end=' ')

        


# 6332032921 1287909 (2020-11-17 09:51)
st = input().strip().lower()

n = int(input())

dic = set()

chk = [-1 for e in range(len(st))]
now = 0

for i in range(n):
    temp = input().strip()
    dic.add(temp)
    
for p in range(len(st) - 1, -1, -1):
    for q in range(len(st) - p + 1):
        invalid = False
        for r in range(q, q + p):
            if chk[r] != -1:
                invalid = True
                break
        if invalid:
            continue
        if st[q: q + p] in dic:
            for r in range(q, q + p):
                chk[r] = now
            now += 1

prev = chk[0]
temp = ''
finalize = []

for q in range(len(chk)):
    if chk[q] == prev:
        temp += st[q]
    else:
        prev = chk[q]
        finalize.append(temp)
        temp = st[q]

finalize.append(temp)

print(' '.join(finalize))


# 6332033521 1288061 (2020-11-17 10:28)
a = input().lower()
n = len(a)
s = set()
l = []
k = int(input())
for i in range(k):
    s.add(input().strip())

i = 0
while i < n:
    #print(i)
    for j in range(n,i,-1):
        temp = a[i:j]
        if temp in s:
            l.append([i,j,temp])
            i = j-1
            break
    i+=1

ans = ""
prev = 0
for i in l:
    #print(i,prev)
    if i[0] != prev:
        ans += str(a[prev:i[0]])
        ans += " "
    ans += i[2]
    ans += " "
    prev = i[1]
if prev != len(a):
    ans += a[prev:]

print(ans.strip())


# 6332034121 1288137 (2020-11-17 10:44)
s = input()
n = int(input())
word = dict()
for i in range(ord('a'),ord('z')+1):
    word[chr(i)] = list()
for i in range(n):
    tmp = input()
    word[tmp[0]].append((len(tmp),tmp))

for i in range(ord('a'),ord('z')+1):
    word[chr(i)].sort(reverse = True)
ans = []
notindict =''
cnt = 0
while cnt < len(s):
    if len(word[s[cnt]]) == 0:
        notindict += s[cnt]
        cnt += 1
    else :
        tmp = ''
        found = False
        choose = ''
        for i in range(min(word[s[cnt]][0][0],len(s)-cnt)):
            tmp += s[cnt+i]
            #print(tmp)
            for b in word[s[cnt]]:
                if tmp == b[1]:
                    found = True
                    choose = tmp
                    break
        if notindict != '' and found:
            ans.append(notindict)
            notindict = ''
        if found:
            ans.append(choose)
            cnt += len(choose)
        elif not found:
            notindict += s[cnt]
            cnt += 1
                
if notindict != '':
    ans.append(notindict)
    notindict = ''
print(' '.join(ans))


    


# 6332035821 1287884 (2020-11-17 09:44)
s = input().lower()
n = int(input())
d = []
for i in range(n):
    d.append(input())
d = sorted(d, key=lambda dd: len(dd), reverse=True)
i = 0
x = []
lch = []
while i<len(s):
    ch = True
    for j in d:
        if s[i:i+len(j)] == j:
            x.append(s[i:i+len(j)])
            i+=len(j)
            ch=False
            break
    if ch:
        x.append(s[i])
        i+=1
for i,a in enumerate(x):
    if i!=len(x)-1 and a not in d and x[i+1] not in d:
        print(a, end='')
    else:
        print(a, end=' ')


# 6332038721 1287938 (2020-11-17 09:58)
def lensort(a) :
    return len(a)
dict = list()
s = input()
s = s.lower()
dictlen = int(input())
for i in range(dictlen) :
    a= input()
    dict.append(a)
dict = sorted(dict,key = lensort,reverse = True)
#print(dict)
itemp = 0
isspace = 0
for i in range(len(s)) :
    found = 0 
#    print(i,itemp)
    if i < itemp : continue
    elif i == itemp : itemp = 0
    for j in range(dictlen) :
        same = 0
        for k in range(len(dict[j])) :
            if i+k >= len(s) :
                same = -1
                break;
            if s[i+k] != dict[j][k] :
                same = -1
                break;
        if same == 0 :
            if isspace == -1 : print(' ',end='')
            print(dict[j],end=' ')
            itemp = i+len(dict[j])
            found = 1
            isspace = 0
            break;
    if found == 0 :
        print(s[i],end='')
        isspace = -1
            
        

    


# 6332039321 1288351 (2020-11-17 11:06)
x=input()
dic=[]
d=x
n=int(input())
kp=[]
ans=[]
x=x.lower()
x=list(x)
for i in range(n):
    wo=input().strip()
    wo=wo.lower()
    dic.append((-len(wo),wo))
dic.sort()
for i in range(n):
    j=0
    while(j<len(x)-len(dic[i][1])+1):
        dic2=list(dic[i][1])
        if(x[j:j+len(dic[i][1])]==dic2):
            kp.append((j,dic[i][1]))
            x[:]=x[0:j]+(['1']*(len(dic[i][1])))+x[j+len(dic[i][1]):]
            j+=len(dic[i][1])
        else:
            j+=1
kp.sort()
cnt=0
cc=[]
if(len(kp)==0):
  print(d)
  exit(0)
if(len(kp)==1):
    if(cnt<kp[0][0]):
        c=''
        for j in range(cnt,kp[0][0]):
            c+=x[j]
        cc.append((cnt,c))
        cnt=kp[0][0]
    if(cnt+len(kp[len(kp)-1][1])<len(x)):
            c=''
            for j in range(cnt+len(kp[len(kp)-1][1]),len(x)):
                c+=x[j]
            cc.append((cnt+len(kp[len(kp)-1][1]),c))
elif(len(kp)>1):
    for i in range(len(kp)-1):
        if(i==0 and cnt<kp[i][0]):
            if(cnt<kp[i][0]):
                c=''
                for j in range(cnt,kp[i][0]):
                    c+=x[j]
            cc.append((cnt,c))
            cnt=kp[i][0]
            if(cnt+len(kp[i][1])<kp[i+1][0]):
                c=''
                for j in range(cnt+len(kp[i][1]),kp[i+1][0]):
                    c+=x[j]
                cc.append((cnt+len(kp[i][1]),c))
            cnt=kp[i+1][0]
        else:
            if(cnt+len(kp[i][1])<kp[i+1][0]):
                c=''
                for j in range(cnt+len(kp[i][1]),kp[i+1][0]):
                    c+=x[j]
                cc.append((cnt+len(kp[i][1]),c))
            cnt=kp[i+1][0]
    if(cnt+len(kp[len(kp)-1][1])<len(x)):
            c=''
            for j in range(cnt+len(kp[len(kp)-1][1]),len(x)):
                c+=x[j]
            cc.append((cnt+len(kp[len(kp)-1][1]),c))
for i in cc:
    kp.append(i)
kp.sort()
for i in range(len(kp)):
    ans.append(kp[i][1])
print(' '.join(ans))

# 6332041521 1296575 (2020-12-08 23:52)
S=input().strip()
a=int(input())
l=list()
for i in range(a) :
  ss=input().strip()
  l.append(ss)
n=len(S)
pos=list()
i=0
F=0
while i<n :
  for j in range(n,i+1,-1) :
    if S[i:j] in l :
      if i==0 :
        F=1
      elif F==0 :
        F=1
        pos.append(0)
      pos.append(i)
      pos.append(j)
      i=j-1
      break
  i+=1
if len(pos)==0 :
  pos.append(0)
if pos[len(pos)-1]!=n :
  pos.append(n)
x=""
N=len(pos)
i=0
for i in range(N-1):
  x=x+S[pos[i]:pos[i+1]]+" "
print(x.strip())