#!/usr/bin/python3

import string

init = input()

Z, P = map(int, input().split(' '))

pravidla = {}
for i in range(Z):
    pismeno, nahrada = input().split(' ')
    pravidla[pismeno] = nahrada

delky = {}

def delka_expanze(c):
    if c in delky:
        return delky[c] # už spočítáno dříve?
    if c in string.digits:
        return 1
    else:
        delka = 0
        for znak in pravidla[c]:
            delka += delka_expanze(znak)
        delky[c] = delka
        return delka

def cislice(s, i):
    pos = 0
    for c in s:
        if c in string.digits:
            if pos == i:
                return c
            else:
                pos += 1
        else:
            delka = delka_expanze(c)
            konec = pos + delka
            if i >= pos and i < konec:
                return cislice(pravidla[c], i - pos)
            else:
                pos = konec
    raise Exception


vysledek = ''
for i in range(P, P+10):
    vysledek += cislice(init, i)
print(vysledek)