import sys,io
from random import *
def findall(s,t):
    n,m=len(s),len(t)
    result=[]
    for i in range(n-m+1):
        if s[i:i+m]==t:
            result.append(i)
    return result
def thue_interactive(program,debug=False):
    program=list(filter(None, map(lambda x: x.replace('\r',''), program.strip('\n').split('\n'))))
    string=''
    rules=[]
    for j,i in enumerate(program):
        if i.startswith('::='):
            string=''.join(program[j+1:])
            break
        if len(i.split('::='))!=2:
            raise SyntaxError('invalid syntax')
        rules.append(tuple(i.split('::=')))
    if debug:
        print(f'Initial string: {string}')
    while 1:
        applicable_rules=[]
        for ruleid,(i,j) in enumerate(rules):
            occurrences=findall(string,i)
            for k in occurrences:
                applicable_rules.append((ruleid,k))
        if not applicable_rules:
            break
        u=choice(applicable_rules)
        ruleid,pos=u
        replacement=rules[ruleid][1]
        if rules[ruleid][1].startswith('~'):
            replacement=''
            print(rules[ruleid][1][1:] if rules[ruleid][1][1:] else '\n',end='')
        elif rules[ruleid][1]==':::':
            replacement=input('Please input a string: 'if debug else '')
        string=string[:pos]+replacement+string[pos+len(rules[ruleid][0]):]
        if debug:
            print(f'Applying rule {ruleid}: Replace {rules[ruleid][0]} at {pos} with {replacement} -> {string}')
    if debug:
        print(f'Final string: {string}')
    return string
def thue(program,inp):
    sys.stdin=io.StringIO(inp)
    sys.stdout=io.StringIO()
    ret=thue_interactive(program)
    return sys.stdout.getvalue()+"\nFinal state string: "+ret