The name of one small but proud corporation consists of n lowercase English letters. The Corporation has decided to try rebranding — an active marketing strategy, that includes a set of measures to change either the brand (both for the company and the goods it produces) or its components: the name, the logo, the slogan. They decided to start with the name.

For this purpose the corporation has consecutively hired m designers. Once a company hires the i-th designer, he immediately contributes to the creation of a new corporation name as follows: he takes the newest version of the name and replaces all the letters x_{i} by y_{i}, and all the letters y_{i} by x_{i}. This results in the new version. It is possible that some of these letters do no occur in the string. It may also happen that x_{i} coincides with y_{i}. The version of the name received after the work of the last designer becomes the new name of the corporation.

Manager Arkady has recently got a job in this company, but is already soaked in the spirit of teamwork and is very worried about the success of the rebranding. Naturally, he can't wait to find out what is the new name the Corporation will receive.

Satisfy Arkady's curiosity and tell him the final version of the name.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the length of the initial name and the number of designers hired, respectively.

The second line consists of n lowercase English letters and represents the original name of the corporation.

Next m lines contain the descriptions of the designers' actions: the i-th of them contains two space-separated lowercase English letters x_{i} and y_{i}.


-----Output-----

Print the new name of the corporation.


-----Examples-----
Input
6 1
police
p m

Output
molice

Input
11 6
abacabadaba
a b
b c
a d
e g
f a
b b

Output
cdcbcdcfcdc



-----Note-----

In the second sample the name of the corporation consecutively changes as follows: $\text{abacabadaba} \rightarrow \text{babcbabdbab}$

$\text{babcbabdbab} \rightarrow \text{cacbcacdcac}$

$\text{cacbcacdcac} \rightarrow \text{cdcbcdcacdc}$

[Image]

[Image]

[Image]

Difficulty: EASY
Tags: String algorithms

Implementation

Starter code:

Solutions:
(n, m) = (int(x) for x in input().split())
s = input()
f = dict(zip('abcdefghijklmnopqrstuvxwyz', 'abcdefghijklmnopqrstuvxwyz'))
t = dict(zip('abcdefghijklmnopqrstuvxwyz', 'abcdefghijklmnopqrstuvxwyz'))
for i in range(m):
	(a, b) = input().split()
	A = t[a]
	B = t[b]
	f[A] = b
	f[B] = a
	t[a] = B
	t[b] = A
for c in s:
	print(f[c], end='')
print()


(N, M) = map(int, input().split())
name = input()
table = [0] * 26
for i in range(26):
	table[i] = i
buffs = []
for _ in range(M):
	(before, after) = map(ord, input().split())
	before -= ord('a')
	after -= ord('a')
	buffs.append((before, after))
buffs.reverse()
for pair in buffs:
	(table[pair[0]], table[pair[1]]) = (table[pair[1]], table[pair[0]])
ret = ''
for ch in name:
	ret += chr(table[ord(ch) - ord('a')] + ord('a'))
print(ret)


(n, m) = map(int, input().split())
s = list(input())
s1 = 'abcdefghijklmnopqrstuvwxyz'
d = {}
for p in s1:
	d[p] = p
for i in range(m):
	(x, y) = input().split()
	for j in d:
		if d[j] == x:
			d[j] = y
		elif d[j] == y:
			d[j] = x
for i in range(n):
	s[i] = d[s[i]]
print(''.join(map(str, s)))


import sys
import string
read = lambda : list(map(int, sys.stdin.readline().split()))
(n, m) = read()
s = sys.stdin.readline().strip()
design = {c: c for c in string.ascii_lowercase}
for i in range(m):
	(a, b) = sys.stdin.readline().split()
	(design[a], design[b]) = (design[b], design[a])
design2 = {b: a for (a, b) in list(design.items())}
print(''.join((design2[c] for c in s)))


(n, m) = map(int, input().split())
line = input()
alphabet = 'abcdefghijklmnopqrstuvwxyz'
vocab = dict()
antivocab = dict()
for x in range(len(alphabet)):
	vocab[alphabet[x]] = alphabet[x]
	antivocab[alphabet[x]] = alphabet[x]
for i in range(m):
	(x, y) = input().split()
	for i in antivocab[x]:
		vocab[i] = y
	for i in antivocab[y]:
		vocab[i] = x
	(antivocab[x], antivocab[y]) = (antivocab[y], antivocab[x])
new = []
for i in range(n):
	new.append(vocab[line[i]])
print(''.join(map(str, new)))


(n, m) = map(int, input().split())
s = list(input())
dic = {}
for i in range(m):
	(x, y) = input().split()
	for j in dic:
		if dic[j] == x:
			dic[j] = y
		elif dic[j] == y:
			dic[j] = x
	if x not in dic:
		dic[x] = y
	if y not in dic:
		dic[y] = x
for i in range(n):
	if s[i] in dic:
		s[i] = dic[s[i]]
print(''.join(s))


import sys
input = sys.stdin.readline
(n, employ) = map(int, input().split())
word = list(input())
letters = 'abcdefghijklmnopqrstuvwxyz'
replacements = list(letters)
for i in range(employ):
	(x, y) = input().split()
	for j in range(26):
		if replacements[j] == x:
			replacements[j] = y
		elif replacements[j] == y:
			replacements[j] = x
for k in range(n):
	word[k] = replacements[letters.find(word[k])]
print(''.join(word))


import itertools as it
import functools
import operator
import collections
import math
import sys
import string

def solve(s, pairs, n, m):
	d = {c: c for c in string.ascii_lowercase}
	for (c1, c2) in pairs:
		for c in string.ascii_lowercase:
			if d[c] == c1:
				d[c] = c2
			elif d[c] == c2:
				d[c] = c1
	return ''.join((d[c] for c in s))

def print_stderr(*args, **kwargs):
	print(*args, file=sys.stderr, **kwargs)

def main():
	[n, m] = [int(i) for i in input().strip().split()]
	s = input().strip()
	assert len(s) == n
	pairs = [tuple(input().strip().split()) for _ in range(m)]
	result = solve(s, pairs, n, m)
	print(result)
main()


import string
(n, m) = map(int, input().split())
s = input()
old = 'abcdefghijklmnopqrstuvwxyz'
new = old
for i in range(m):
	(x, y) = map(str, input().split())
	new = new.translate(''.maketrans(x + y, y + x))
print(s.translate(''.maketrans(old, new)))


def solve():
	(N, M) = list(map(int, input().split()))
	name = input()
	td = {}
	for c in 'abcdefghijklmnopqrstuvwxyz':
		td[c] = c
	for i in range(M):
		(p, m) = input().split()
		if p == m:
			continue
		pt = td[p]
		mt = td[m]
		del td[p]
		del td[m]
		td[m] = pt
		td[p] = mt
	nd = {f: t for (t, f) in list(td.items())}
	ans = ''.join([nd[c] for c in name])
	print(ans)

def __starting_point():
	solve()
__starting_point()


x = input().split()
length = int(x[0])
num = int(x[1])
name = input()
trans = [0] * num
for i in range(num):
	trans[i] = input().split()
trans_final = {}
for i in range(97, 123):
	c = chr(i)
	x = c
	for j in range(len(trans)):
		if x in trans[j]:
			if x == trans[j][0]:
				x = trans[j][1]
			else:
				x = trans[j][0]
	trans_final[c] = x
new_name = [0] * length
for i in range(length):
	new_name[i] = trans_final[name[i]]
print(''.join(new_name))


from string import ascii_lowercase as asc
g = {}
(n, m) = map(int, input().split())
ans = [''] * n
s = input()
for i in asc:
	g[i] = []
for i in range(n):
	g[s[i]] += [i]
for i in range(m):
	(a, b) = input().split()
	ga = g.get(a)
	gb = g.get(b)
	g[b] = ga
	g[a] = gb
for i in g:
	for j in g[i]:
		ans[j] = i
print(''.join(ans))


(n, k) = map(int, input().split())
s = input()
(alp1, alp2) = ('', '')
for i in range(ord('a'), ord('z') + 1):
	alp1 += chr(i)
for i in range(ord('a'), ord('z') + 1):
	alp2 += chr(i)
for i in range(k):
	(a, b) = map(str, input().split())
	alp2 = alp2.replace(a, b.upper())
	alp2 = alp2.replace(b, a)
	alp2 = alp2.lower()
for i in range(26):
	s = s.replace(alp1[i], alp2[i].upper())
print(s.lower().strip('\n'))


from sys import stdin, stdout
(a, b) = map(int, stdin.readline().split())
z = stdin.readline().replace('', ' ').split()
ans_digit = [*range(27)]
for _ in ' ' * b:
	(c, d) = map(str, stdin.readline().split())
	(ans_digit[ord(c) - 97], ans_digit[ord(d) - 97]) = (ans_digit[ord(d) - 97], ans_digit[ord(c) - 97])
ans_char = []
for i in range(27):
	w = ans_digit[i]
	p = i
	while w != i:
		p = w
		w = ans_digit[w]
	ans_char += [p]
for i in range(a):
	z[i] = chr(97 + ans_char[ord(z[i]) - 97])
stdout.write(''.join(z))


(n, m) = map(int, input().split())
in_s = input()
renames_str = [input() for i in range(m)]
rule = {}
rule_inv = {}
for i in range(26):
	c = chr(ord('a') + i)
	rule[c] = c
	rule_inv[c] = c
for x in renames_str:
	(a, b) = x.split()
	for (k, v) in rule.items():
		if v == a:
			rule[k] = b
		if v == b:
			rule[k] = a
for c in in_s:
	print(rule[c], end='')
print()


from sys import stdin, stdout
input = stdin.readline
d = {'x': 'x', 'y': 'y', 'z': 'z', 'p': 'p', 'q': 'q', 'r': 'r', 's': 's', 't': 't', 'u': 'u', 'v': 'v', 'w': 'w', 'h': 'h', 'i': 'i', 'j': 'j', 'k': 'k', 'l': 'l', 'm': 'm', 'n': 'n', 'o': 'o', 'a': 'a', 'b': 'b', 'c': 'c', 'd': 'd', 'e': 'e', 'f': 'f', 'g': 'g'}
(n, m) = list(map(int, input().split()))
s = input()
xy = [input() for i in range(m)]
for i in d:
	t = i
	for j in xy:
		if j[0] == t:
			t = j[2]
		elif j[2] == t:
			t = j[0]
	d[i] = t
for i in range(n):
	stdout.write(d[s[i]])


letterlist = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
import sys
input = sys.stdin.readline
(llength, queries) = list(map(int, input().split()))
name = input()
countlist = [[] for i in range(26)]
ogname = ['' for i in range(llength)]
for i in range(llength):
	countlist[letterlist.index(name[i])].append(i)
for i in range(queries):
	repl = input().split()
	meow = letterlist.index(repl[0])
	bark = letterlist.index(repl[1])
	saus = countlist[meow]
	corgi = countlist[bark]
	countlist[meow] = corgi
	countlist[bark] = saus
for i in range(26):
	for q in countlist[i]:
		ogname[q] = letterlist[i]
print(''.join(ogname))


(n, m) = map(int, input().split())
s = list(input())
d = {i: i for i in 'qwertyuiopasdfghjklzxcvbnm'}
for _ in range(m):
	(x, y) = input().split()
	(d[x], d[y]) = (d[y], d[x])
d = {value: key for (key, value) in d.items()}
for i in range(n):
	s[i] = d[s[i]]
print(''.join(s))


g = {}
(n, m) = map(int, input().split())
p = [0] * n
s = input()
for i in 'qwertyuiopasdfghjklzxcvbnm':
	g[i] = []
for i in range(n):
	g[s[i]] += [i]
for i in range(m):
	(a, b) = input().split()
	(g[a], g[b]) = (g[b], g[a])
for i in g:
	for j in g[i]:
		p[j] = i
print(''.join(p))


from sys import stdin, stdout
import math, sys
from itertools import permutations, combinations
from collections import defaultdict, deque, OrderedDict
from os import path
import bisect as bi
import heapq

def yes():
	print('YES')

def no():
	print('NO')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

	def I():
		return int(input())

	def In():
		return map(int, input().split())
else:

	def I():
		return int(stdin.readline())

	def In():
		return map(int, stdin.readline().split())

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_right(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		(n, m) = In()
		l = list(input())
		d = defaultdict(list)
		for x in range(n):
			d[l[x]].append(x)
		for i in range(m):
			(a, b) = input().split(' ')
			(d[a], d[b]) = (d[b], d[a])
		ans = [''] * n
		for x in d:
			for i in d[x]:
				ans[i] = x
		print(''.join(ans))
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


import sys
(size, swaps) = map(int, sys.stdin.readline().split())
word = sys.stdin.readline()
alp = 'abcdefghijklmnopqrstuvwxyz'
alp2 = 'abcdefghijklmnopqrstuvwxyz'
for i in range(swaps):
	(a, b) = map(str, sys.stdin.readline().split())
	alp2 = alp2.replace(a, b.upper())
	alp2 = alp2.replace(b, a)
	alp2 = alp2.lower()
for i in range(26):
	word = word.replace(alp[i], alp2[i].upper())
sys.stdout.write(word.lower().strip('\n'))


from sys import stdin
from sys import exit
live = True
if not live:
	stdin = open('data.in', 'r')
(n, m) = list(map(int, stdin.readline().strip().split()))
name = stdin.readline().strip()
switch = list('abcdefghijklmnopqrstuvwxyz')
pos = list(range(26))
for it in range(m):
	(x, y) = list(map(str, stdin.readline().strip().split()))
	posX = ord(x) - 97
	posY = ord(y) - 97
	switch[pos[posX]] = y
	switch[pos[posY]] = x
	temp = pos[posX]
	pos[posX] = pos[posY]
	pos[posY] = temp
for it in name:
	print(switch[ord(it) - 97], end='')
if not live:
	stdin.close()


import string
(n, m) = list(map(int, input().split()))
alf = list(string.ascii_lowercase)
s = input()
for i in range(m):
	(x, y) = input().split()
	index1 = alf.index(x)
	index2 = alf.index(y)
	(alf[index1], alf[index2]) = (alf[index2], alf[index1])
for i in s:
	print(alf[ord(i) - ord('a')], end='')


import string
(n, m) = map(int, input().split())
s = input()
chars = string.ascii_lowercase
for _ in range(m):
	(a, b) = input().split()
	chars = chars.replace(a, '%').replace(b, a).replace('%', b)
replacements = {ord(string.ascii_lowercase[i]): chars[i] for i in range(26)}
print(s.translate(replacements))


import string
(n, m) = input().split()
(n, m) = [int(n), int(m)]
name = input()
name = list(name)
buffer = {}
for ch in list(string.ascii_lowercase):
	buffer[ch] = []
for i in range(n):
	buffer[name[i]].append(i)
for j in range(m):
	(xi, yi) = input().split()
	temp = buffer[xi]
	buffer[xi] = buffer[yi]
	buffer[yi] = temp
for (key, value) in list(buffer.items()):
	for i in value:
		name[i] = key
name = ''.join(name)
print(name)


import sys
import string
lines = sys.stdin.readlines()
(m, n) = map(int, lines[0].split())
s = list(map(lambda x: ord(x) - ord('a'), lines[1]))[:-1]
r = [c for c in string.ascii_lowercase]
for i in range(n):
	(x, y) = (lines[2 + i][0], lines[2 + i][2])
	for j in range(26):
		if r[j] == x:
			r[j] = y
		elif r[j] == y:
			r[j] = x
for i in range(m):
	s[i] = r[s[i]]
print(''.join(s))


(n, m) = map(int, input().split())
s = input()
repos = {}
ans = [[] for i in range(n)]
for i in range(len(s)):
	if s[i] in repos:
		repos[s[i]].append(i)
	else:
		repos[s[i]] = [i]
for i in range(m):
	(charbefore, charafter) = input().split()
	if charafter in repos and charbefore in repos:
		(repos[charbefore], repos[charafter]) = (repos[charafter], repos[charbefore])
	elif charbefore in repos:
		(repos[charbefore], repos[charafter]) = ([], repos[charbefore])
	elif charafter in repos:
		(repos[charbefore], repos[charafter]) = (repos[charafter], [])
	else:
		(repos[charafter], repos[charbefore]) = ([], [])
for i in repos:
	if repos[i]:
		for j in repos[i]:
			ans[j] = i
print(''.join(ans))


(n, m) = map(int, input().split())
st = input()
d = {}
import string
for x in string.ascii_lowercase:
	d[x] = []
for i in range(n):
	d[st[i]].append(i)
for i in range(m):
	(x, y) = input().split()
	(d[x], d[y]) = (d[y], d[x])
ans = [0] * n
for x in d:
	for y in d[x]:
		ans[y] = x
print(''.join(ans))


IL = lambda : list(map(int, input().split()))
IS = lambda : input().split()
I = lambda : int(input())
S = lambda : input()
(n, m) = IL()
name = S()
letters = dict([[chr(i), chr(i)] for i in range(97, 123)])
for i in range(m):
	(l1, l2) = IS()
	(letters[l1], letters[l2]) = (letters[l2], letters[l1])
rletters = {v: k for (k, v) in letters.items()}
print(''.join([rletters[l] for l in name]))


import string
(N, M) = map(int, input().split())
S = input()
dic = string.ascii_lowercase
for _ in range(M):
	(x, y) = input().split()
	dic = dic.translate(str.maketrans(x + y, y + x))
print(S.translate(str.maketrans(string.ascii_lowercase, dic)))


(n, m) = map(int, input().split())
s = input()
s1 = ''
for i in range(ord('a'), ord('z') + 1):
	s1 += chr(i)
s2 = s1 + ''
for i in range(m):
	(a, b) = input().split()
	s2 = s2.replace(a, '*')
	s2 = s2.replace(b, a)
	s2 = s2.replace('*', b)
ss = ''
for i in range(n):
	ss += s2[s1.index(s[i])]
print(ss)


(n, m) = list(map(int, input().split()))
s = input()
orig = 'abcdefghijklmnopqrstuvwxyz'
after = orig
for _ in range(m):
	(xi, yi) = input().split()
	after = after.translate(str.maketrans(xi + yi, yi + xi))
print(s.translate(str.maketrans(orig, after)))


(n, m) = map(int, input().split())
s = input()
l = [chr(ord('a') + i) for i in range(26)]
for i in range(m):
	(a, b) = input().split()
	for j in range(26):
		if l[j] == a:
			l[j] = b
		elif l[j] == b:
			l[j] = a
print(''.join([l[ord(k) - ord('a')] for k in s]))


(n, m) = [int(i) for i in input().split()]
s = input()
x = [''] * m
y = [''] * m
for i in range(m):
	(x[i], y[i]) = [i for i in input().split()]
letter = [[] for i in range(26)]
for i in range(n):
	letter[ord(s[i]) - ord('a')].append(i)
for i in range(m):
	(letter[ord(x[i]) - ord('a')], letter[ord(y[i]) - ord('a')]) = (letter[ord(y[i]) - ord('a')], letter[ord(x[i]) - ord('a')])
s_ans = [''] * n
for i in range(26):
	for j in range(len(letter[i])):
		s_ans[letter[i][j]] = chr(i + ord('a'))
print(''.join(s_ans))


(n, m) = map(int, input().split())
alpha_cnst = list('abcdefghijklmnopqrstuvwxyz')
alpha = list('abcdefghijklmnopqrstuvwxyz')
s = input()
for i in range(m):
	(a, b) = input().split()
	for j in range(len(alpha)):
		if alpha[j] == a:
			alpha[j] = b
		elif alpha[j] == b:
			alpha[j] = a
total = ''
for char in s:
	total += alpha[alpha_cnst.index(char)]
print(total)


import sys
import string
from collections import Counter, defaultdict
from math import fsum, sqrt, gcd, ceil, factorial
from operator import *
from itertools import accumulate
inf = float('inf')
flush = lambda : sys.stdout.flush
comb = lambda x, y: factorial(x) // factorial(y) // factorial(x - y)
ip = lambda : input()
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
(n, k) = r()
s = ip()
arr = {i: i for i in string.ascii_lowercase}

def get_key(arr, val):
	for (i, j) in arr.items():
		if j == val:
			return i
for _ in range(k):
	(a, b) = ip().split()
	if a == b:
		continue
	x = get_key(arr, a)
	y = get_key(arr, b)
	temp = arr[x]
	arr[x] = arr[y]
	arr[y] = temp
for i in s:
	print(arr[i], end='')


s = list('abcdefghijklmnopqrstuvwxyz')
(n, m) = tuple(map(int, input().split()))
name = input()
name_num = [s.index(name[i]) for i in range(n)]
for i in range(m):
	(a, b) = input().split()
	(a, b) = (s.index(a), s.index(b))
	(s[a], s[b]) = (s[b], s[a])
for elem in name_num:
	print(s[elem], end='')


import string
(n, m) = map(int, input().split())
s = input()
s1 = string.ascii_lowercase
for i in range(m):
	(x, y) = input().split()
	s1 = s1.translate(str.maketrans(x + y, y + x))
print(s.translate(str.maketrans(string.ascii_lowercase, s1)))


(n, m) = map(int, input().split())
alph = list('abcdefghijklmnopqrstuvwxyz')
index = [int(i) for i in range(26)]
s = input()
for i in range(m):
	(a, b) = input().split()
	a_index = index[ord(a) - ord('a')]
	b_index = index[ord(b) - ord('a')]
	alph[a_index] = b
	alph[b_index] = a
	index[ord(a) - ord('a')] = b_index
	index[ord(b) - ord('a')] = a_index
for i in s:
	print(alph[ord(i) - ord('a')], end='')
print('')


from string import ascii_lowercase
l = ascii_lowercase
[n, m] = list(map(int, input().split()))
s = input()
a = [None] * n
for i in range(n):
	a[i] = l.index(s[i])
alpha = [i for i in range(26)]
for i in range(m):
	(al, bl) = input().split()
	ai = l.index(al)
	bi = l.index(bl)
	ai = alpha.index(ai)
	bi = alpha.index(bi)
	(alpha[ai], alpha[bi]) = (alpha[bi], alpha[ai])
for i in range(n):
	print(l[alpha[a[i]]], end='')
print()


from sys import stdin
let_a = ord('a')
letters = [0] * 26
for i in range(0, 26):
	letters[i] = chr(let_a + i)
(n, m) = [int(x) for x in stdin.readline().split()]
s = stdin.readline().strip()
i = 0
while i < m:
	(a, b) = stdin.readline().split()
	if a[0] != b[0]:
		(letters[ord(a[0]) - let_a], letters[ord(b[0]) - let_a]) = (letters[ord(b[0]) - let_a], letters[ord(a[0]) - let_a])
	i += 1
replace = [0] * 26
for i in range(0, 26):
	replace[ord(letters[i]) - let_a] = chr(let_a + i)
for c in s:
	print(replace[ord(c) - let_a], end='')


from math import sqrt, ceil, floor
from sys import stdin, stdout
from heapq import heapify, heappush, heappop
import string
(n, m) = map(int, stdin.readline().split())
a = stdin.readline()
l = list(string.ascii_lowercase)
z = [[] for i in range(26)]
for i in range(n):
	z[ord(a[i]) - ord('a')].append(i)
for i in range(m):
	(tmp1, tmp2) = stdin.readline().split()
	le = l.index(tmp1)
	re = l.index(tmp2)
	(l[le], l[re]) = (l[re], l[le])
ans = [' '] * n
for i in range(26):
	for j in range(len(z[i])):
		ans[z[i][j]] = l[i]
for i in range(n):
	stdout.write(ans[i])


from string import ascii_lowercase as ascii
(n, m) = (int(x) for x in input().split())
s = input()
f = dict(zip(ascii, ascii))
t = dict(zip(ascii, ascii))
for i in range(m):
	(a, b) = input().split()
	A = t[a]
	B = t[b]
	f[A] = b
	f[B] = a
	t[a] = B
	t[b] = A
for c in s:
	print(f[c], end='')
print()


import sys
input = sys.stdin.readline
(n, m) = input().split()
m = int(m)
name = input()
letters = 'qwertyuiopasdfghjklzxcvbnm'
letters1 = 'qwertyuiopasdfghjklzxcvbnm'
for i in range(m):
	(let1, let2) = input().split()
	letters = letters.replace(let1, let2.upper())
	letters = letters.replace(let2, let1.upper())
	letters = letters.lower()
for i in range(len(letters)):
	name = name.replace(letters1[i], letters[i].upper())
print(name.lower())


(n, m) = list(map(int, input().split()))
ch = str(input())
res = [ch[k] for k in range(n)]
X = ['' for _ in range(m)]
Y = ['' for _ in range(m)]
for k in range(m):
	s = str(input())
	X[k] = s[0]
	Y[k] = s[2]
al = 'abcdefghijklmnopqrstuvwxyz'
A = [al[k] for k in range(26)]
B = A[:]
for k in range(m):
	a = A.index(X[k])
	b = A.index(Y[k])
	c = A[a]
	A[a] = A[b]
	A[b] = c
for j in range(n):
	a = B.index(res[j])
	res[j] = A[a]
ch = ''
for k in range(n):
	ch = ch + res[k]
print(ch)


(n, m) = list(map(int, input().split(' ')[:2]))
s = input()[:n]
ls = {}
for c in s:
	ls[c] = c
for i in range(m):
	(x, y) = input().split(' ')[:2]
	if x not in ls:
		ls[x] = x
	if y not in ls:
		ls[y] = y
	(ls[x], ls[y]) = (ls[y], ls[x])
rev = {}
for (c, v) in list(ls.items()):
	rev[v] = c
print(''.join([rev[c] for c in s]))


(n, m) = [int(_) for _ in input().split()]
convert = 'abcdefghijklmnopqrstuvwxyz'
s = input()
for i in range(m):
	(x, y) = input().split()
	convert = convert.replace(x, '*')
	convert = convert.replace(y, x)
	convert = convert.replace('*', y)
abc = 'abcdefghijklmnopqrstuvwxyz'
for i in range(n):
	print(convert[abc.find(s[i])], end='')
print()


(n, m) = map(int, input().split())
S = input()
char = {chr(i): chr(i) for i in range(ord('a'), ord('z') + 1)}
keys = char.keys()
for i in range(m):
	(x, y) = input().split()
	for c in keys:
		if char[c] == x:
			char[c] = y
		elif char[c] == y:
			char[c] = x
ans = []
for c in list(S):
	ans.append(char[c])
print(''.join(ans))


def dict_find(d, value):
	for (k, v) in d.items():
		if v == value:
			return k
(n, m) = map(int, input().split())
s = input()
d = {chr(c): chr(c) for c in range(ord('a'), ord('z') + 1)}
for _ in range(m):
	(x, y) = input().split()
	c1 = dict_find(d, x)
	c2 = dict_find(d, y)
	(d[c1], d[c2]) = (d[c2], d[c1])
for character in s:
	print(d[character], end='')
print()


A = list('abcdefghijklmnopqrstuvwxyz')
(n, m) = map(int, input().split())
name = input()
for i in range(m):
	s = input()
	(x, y) = (s[0], s[2])
	x_index = A.index(x)
	y_index = A.index(y)
	(A[x_index], A[y_index]) = (A[y_index], A[x_index])
for c in name:
	index = ord(c) - ord('a')
	print(A[index], end='')


(n, m) = [int(x) for x in input().split(' ')]
name = input().strip()

def findChanges(D, x, y):
	changes = []
	if x not in D:
		changes.append((x, y))
	for (k, v) in D.items():
		if v == x:
			changes.append((k, y))
	return changes
D = {}
for i in range(m):
	(x, y) = input().split(' ')
	changes = findChanges(D, x, y)
	changes += findChanges(D, y, x)
	for (a, b) in changes:
		D[a] = b
out = []
for l in name:
	if l in D:
		l = D[l]
	out.append(l)
print(''.join(out))


import string

def mp():
	return map(int, input().split())

def lt():
	return list(map(int, input().split()))

def pt(x):
	print(x)
(n, m) = mp()
s = input()
s1 = string.ascii_lowercase
for i in range(m):
	L = input().split()
	(a, b) = (L[0], L[1])
	s1 = s1.translate(str.maketrans(a + b, b + a))
pt(s.translate(str.maketrans(string.ascii_lowercase, s1)))


(n, m) = map(int, input().split())
name = list(input())
letters = list('abcdefghijklmnopqrstuvwxyz')
for i in range(m):
	(x, y) = input().split()
	(xi, yi) = (-1, -1)
	for (i, v) in enumerate(letters):
		if x == v:
			xi = i
		if y == v:
			yi = i
	(letters[xi], letters[yi]) = (letters[yi], letters[xi])
print(''.join((letters[ord(i) - ord('a')] for i in name)))


(n, m) = map(int, input().split())
s = input()
d = {}
for i in range(m):
	(a, b) = input().split()
	for k in d:
		if d[k] == a:
			d[k] = b
		elif d[k] == b:
			d[k] = a
	if a not in d:
		d[a] = b
	if b not in d:
		d[b] = a
r = ''
for c in s:
	if c in d:
		r += d[c]
	else:
		r += c
print(r)


c = 26 * [0]
ind = 26 * [0]
for i in range(26):
	c[i] = chr(i + 97)
	ind[i] = i
(n, m) = map(int, input().split())
s = input()
size = len(s)
s1 = size * [0]
for _ in range(m):
	(x, y) = input().split()
	c[ind[ord(x) - 97]] = y
	c[ind[ord(y) - 97]] = x
	(ind[ord(x) - 97], ind[ord(y) - 97]) = (ind[ord(y) - 97], ind[ord(x) - 97])
for i in range(size):
	s1[i] = c[ord(s[i]) - 97]
print(''.join(s1))


from collections import *
from sys import *
input = stdin.readline
d = defaultdict(list)
(n, m) = map(int, input().split())
s = input()
flag = 0
flag2 = 0
(temp, temp1) = (0, 0)
for i in range(m):
	(x, y) = input().strip().split(' ')
	if x in d.keys():
		flag = 1
		for i in d.keys():
			if d[i] == x:
				temp = i
				break
	else:
		flag = 0
		d[x] = y
	if y in d.keys():
		flag2 = 1
		for i in d.keys():
			if d[i] == y:
				temp1 = i
				break
	else:
		flag2 = 0
		d[y] = x
	if flag == 1:
		d[temp] = y
	if flag2 == 1:
		d[temp1] = x
for i in s:
	if d[i] != []:
		print(d[i], end='')
	else:
		print(i, end='')


import string
(n, m) = map(int, input().split())
brand = [c for c in input()]
ocr = {c: [] for c in string.ascii_lowercase}
for i in range(n):
	ocr[brand[i]].append(i)
changes = []
for _ in range(m):
	changes.append([c for c in input().split()])
for change in changes:
	hold1 = ocr[change[0]]
	hold2 = ocr[change[1]]
	ocr[change[0]] = hold2
	ocr[change[1]] = hold1
newbrand = [''] * n
for key in ocr.keys():
	for i in ocr[key]:
		newbrand[i] = key
print(''.join(newbrand))


__author__ = 'artyom'

def main():
	z = {}
	for i in range(26):
		z[chr(i + 97)] = chr(i + 97)
	(n, m) = read(3)
	s = read(0)
	for _ in range(m):
		(f, t) = read(2)
		(z[t], z[f]) = (z[f], z[t])
	repl = [0] * 26
	for (key, val) in z.items():
		repl[ord(val) - 97] = key
	r = ''
	for c in s:
		r += repl[ord(c) - 97]
	return r

def read(mode=1, size=None):
	if mode == 0:
		return input().strip()
	if mode == 1:
		return int(input().strip())
	if mode == 2:
		return input().strip().split()
	if mode == 3:
		return list(map(int, input().strip().split()))
	a = []
	for _ in range(size):
		a.append(read(3))
	return a

def write(s='\n'):
	if s is None:
		s = ''
	if isinstance(s, tuple) or isinstance(s, list):
		s = ' '.join(map(str, s))
	s = str(s)
	print(s, end='\n')
write(main())


(a, b) = (int(i) for i in input().split())
str = input()
import string
g = {c: c for c in string.ascii_lowercase}
for j in range(b):
	(c, e) = (t for t in input().split())
	(g[c], g[e]) = (g[e], g[c])
r = {b: a for (a, b) in g.items()}
for j in str:
	if j in r.keys():
		print(r[j], end='')
	else:
		print(j, end='')


from math import sqrt, pow, log, log2, log10, exp
from copy import deepcopy
from fractions import gcd

def read_ints():
	return list(map(int, input().split()))

def read_int():
	return read_ints()[0]

def read_floats():
	return list(map(float, input().split()))

def read_float():
	return read_floats()[0]

def format_list(l):
	return ' '.join(list(map(str, l)))

def one_dim_array(n, value=0):
	return [deepcopy(value) for x in range(n)]

def two_dim_array(n, m, value=0):
	return [[deepcopy(value) for x in range(m)] for x in range(n)]

def is_prime(n):
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	for i in range(3, sqrt(n) + 1):
		if n % i == 0:
			return False
	return True

def max_len_sublist(l, f):
	(start, max_length, length) = (0, 0, 0)
	for i in range(1, len(l)):
		if f(l[i], l[i - 1]):
			length += 1
		else:
			if max_length < length:
				start = i - length
				max_length = length
			length = 0
	return (start, max_length)

def tf_to_yn(b):
	return 'YES' if b else 'NO'

def longest_non_descent_subsequence(s, restore_sequence=False):
	d = one_dim_array(len(s), 0)
	for i in range(len(s)):
		possible = [d[j] + 1 if s[j] <= s[i] else 1 for j in range(i)]
		d[i] = 1 if len(possible) == 0 else max(possible)
	if not restore_sequence:
		return d[-1] if len(d) != 0 else 0

def update_ch(ch, f, t):
	addedf = False
	addedt = False
	for key in ch.keys():
		value = ch[key]
		if value == f:
			ch[key] = t
			addedf = True
		if value == t:
			ch[key] = f
			addedt = True
	if not addedf:
		ch[f] = t
	if not addedt:
		ch[t] = f
	return ch
(n, m) = read_ints()
s = list(input())
ch = {}
for i in range(1, m + 1):
	(f, t) = input().split()
	if f != t:
		update_ch(ch, f, t)

def map_with_ch(ch, x):
	if x in ch:
		return ch[x]
	else:
		return x
print(''.join(list(map(lambda x: map_with_ch(ch, x), s))))


import string
(n, m) = map(int, input().split())
s = input()
di = string.ascii_lowercase
for i in range(m):
	(old, new) = input().split()
	a = str.maketrans(old + new, new + old)
	di = di.translate(a)
t = str.maketrans(string.ascii_lowercase, di)
print(s.translate(t))


(n, m) = map(int, input().split())
s = input()
k = []
a = ['' for i in range(m)]
b = ['' for i in range(m)]
ans = [0 for i in range(n)]
for i in range(n):
	k.append(s[i])
d = {}
for i in range(26):
	d[chr(ord('a') + i)] = 0
for i in range(m):
	(a[i], b[i]) = map(str, input().split())
for i in range(26):
	cur = chr(ord('a') + i)
	for j in range(m):
		if a[j] == cur or b[j] == cur:
			if a[j] == cur:
				cur = b[j]
			else:
				cur = a[j]
	d[chr(ord('a') + i)] = cur
used = [True for i in range(n)]
for i in range(26):
	for j in range(n):
		if s[j] == chr(ord('a') + i) and used[j] == True:
			ans[j] = d[chr(ord('a') + i)]
			used[j] = False
print(''.join((str(i) for i in ans)))


(n, m) = [int(x) for x in input().split()]
name = input()
alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for i in range(m):
	(x, y) = input().split()
	indexX = alphabet.index(x)
	indexY = alphabet.index(y)
	(alphabet[indexX], alphabet[indexY]) = (alphabet[indexY], alphabet[indexX])
newName = ''
for character in name:
	newName += alphabet[ord(character) - 97]
print(newName)


alf = list('abcdefghijklmnopqrstuvwxyz')
(n, m) = map(int, input().split())
s = input()
for i in range(m):
	(x, y) = input().split()
	index1 = alf.index(x)
	index2 = alf.index(y)
	(alf[index1], alf[index2]) = (alf[index2], alf[index1])
for i in s:
	print(alf[ord(i) - ord('a')], end='')


def to_list(s):
	return list(map(lambda x: int(x), s.split(' ')))

def to_switch(s):
	return s[0] + s[-1]

def get_letter_dict(switches):
	alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
	letter_dict = {}
	for letter in alphabet:
		curr_letter = letter
		for switch in switches:
			if curr_letter in switch:
				if switch[0] == curr_letter:
					curr_letter = switch[1]
				else:
					curr_letter = switch[0]
		letter_dict[letter] = curr_letter
	return letter_dict

def rebrand(s, letter_dict):
	out_s = ''
	for item in s:
		out_s += letter_dict[item]
	return out_s
(n, m) = to_list(input())
s = input()
switches = []
for i in range(m):
	switches.append(to_switch(input()))
letter_dict = get_letter_dict(switches)
print(rebrand(s, letter_dict))


inn = lambda : int(input())
inm = lambda : map(int, input().split())
ins = lambda : str(input())
ina = lambda : list(map(int, input().split()))
import string

def solve():
	(n, m) = inm()
	s = ins()
	c = {}
	for i in string.ascii_lowercase:
		c[i] = i
	for i in range(m):
		(a, b) = map(str, input().split())
		for j in c.keys():
			if c[j] == a:
				c[j] = b
			elif c[j] == b:
				c[j] = a
	t = ''
	for i in s:
		t += c[i]
	print(t)

def main():
	t = 1
	for _ in range(t):
		solve()
main()


s = input()
a = s.split(' ')
(n, m) = (int(a[0]), int(a[1]))
corpname = input()
us = set(list(corpname))
ds = {}
for i in us:
	ds.update({i: i})
while m > 0:
	m -= 1
	s = input()
	a = s.split(' ')
	(x, y) = (a[0], a[1])
	if x != y:
		for i in ds:
			if ds[i] == x:
				ds[i] = y
			elif ds[i] == y:
				ds[i] = x
cn = ''
for i in corpname:
	cn += ds[i]
print(cn)


from string import ascii_lowercase
dct = {}
for c in ascii_lowercase:
	dct[c] = c
(n, m) = map(int, input().split())
s = list(input())
for _ in range(m):
	(x, y) = input().split()
	xarr = [k for (k, c) in dct.items() if c == x]
	yarr = [k for (k, c) in dct.items() if c == y]
	for c in xarr:
		dct[c] = y
	for c in yarr:
		dct[c] = x
for (i, c) in enumerate(s):
	s[i] = dct[c]
print(''.join(s))


import string
(n, m) = map(int, input().split())
s = list(input().strip())
encode = {ch: ch for ch in string.ascii_lowercase}
for i in range(m):
	(x, y) = input().split()
	t = encode[x]
	encode[x] = encode[y]
	encode[y] = t
inverse = {ch: ch for ch in string.ascii_lowercase}
for (key, value) in encode.items():
	inverse[value] = key
for (i, ch) in enumerate(s):
	s[i] = inverse[ch]
print(''.join(s))


import sys
(n, m) = map(int, sys.stdin.readline().split())
name = list(sys.stdin.readline())
letters = 'abcdefghijklmnopqrstuvwxyz'
replacement = list(letters)
for i in range(m):
	(a, b) = sys.stdin.readline().split()
	for j in range(26):
		if replacement[j] == a:
			replacement[j] = b
		elif replacement[j] == b:
			replacement[j] = a
for i in range(n):
	name[i] = replacement[letters.index(name[i])]
print(''.join(name))


(n, m) = list(map(int, input().split()))
s = input()
p = [chr(i) for i in range(97, 97 + 26)]
for i in range(m):
	(a, b) = input().split()
	for i in range(26):
		if p[i] == a:
			p[i] = b
		elif p[i] == b:
			p[i] = a
print(''.join([p[ord(x) - 97] for x in s]))


(n, m) = [int(x) for x in input().split()]
st = input()
d = {}
ch = 'a'
for i in range(26):
	d[ch] = ch
	ch = chr(ord(ch) + 1)
for i in range(m):
	(x, y) = [z for z in input().split()]
	temp = d[x]
	d[x] = d[y]
	d[y] = temp
answer = []
newd = {}
for key in d:
	value = d[key]
	newd[value] = key
for ch in st:
	answer.append(newd[ch])
print(''.join(answer))


(n, m) = map(int, input().split())
s = [c for c in input()]
d = {}
for i in range(n):
	if s[i] in d:
		d[s[i]].append(i)
	else:
		d[s[i]] = [i]
for _ in range(m):
	(x, y) = input().split()
	if x == y or (x not in d and y not in d):
		continue
	elif x in d and y in d:
		(d[x], d[y]) = (d[y], d[x])
	elif x in d and y not in d:
		d[y] = d[x]
		del d[x]
	elif x not in d and y in d:
		d[x] = d[y]
		del d[y]
ans = [''] * len(s)
for (k, v) in d.items():
	for i in v:
		ans[i] = k
print(''.join(ans))


import math
from decimal import Decimal

def na():
	n = int(input())
	b = [int(x) for x in input().split()]
	return (n, b)

def nab():
	n = int(input())
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	return (n, b, c)

def dv():
	(n, m) = map(int, input().split())
	return (n, m)

def dva():
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	return (n, m, b)

def eratosthenes(n):
	sieve = list(range(n + 1))
	for i in sieve:
		if i > 1:
			for j in range(i + i, len(sieve), i):
				sieve[j] = 0
	return sorted(set(sieve))

def nm():
	n = int(input())
	b = [int(x) for x in input().split()]
	m = int(input())
	c = [int(x) for x in input().split()]
	return (n, b, m, c)

def dvs():
	n = int(input())
	m = int(input())
	return (n, m)
(n, m) = map(int, input().split())
s = input()
d = {}
for i in range(97, 123):
	d[chr(i)] = chr(i)
for i in range(m):
	(x, y) = input().split()
	(d[x], d[y]) = (d[y], d[x])
new = ''
t = {}
for i in d:
	t[d[i]] = i
for i in s:
	new += t[i]
print(new)


(ds, dz) = map(int, input().split())
s = input()
ls = {}
for c in range(97, 123):
	ls[chr(c)] = chr(c)
for i in range(dz):
	(x, y) = input().split(' ')[:2]
	(ls[x], ls[y]) = (ls[y], ls[x])
rev = {}
for (c, v) in ls.items():
	rev[v] = c
print(''.join([rev[c] for c in s]))


(m, n) = map(int, input().split())
s = input()
d = {}
for _ in range(n):
	(x, y) = input().split()
	if x != y:
		(d[x], d[y]) = (d.get(y, y), d.get(x, x))
dd = {}
for x in d:
	dd[d[x]] = x
print(''.join((dd.get(x, x) for x in s)))


d = {}
j = {}
for i in range(26):
	a = chr(i + 97)
	d[a] = a
(n, m) = map(int, input().split())
s = input()
for i in range(m):
	(l, k) = input().split()
	for i in d:
		if d[i] == l:
			d[i] = k
		elif d[i] == k:
			d[i] = l
for i in s:
	print(d[i], end='')


import sys
import math
import itertools
import functools
import collections
import operator
import fileinput
import copy
ORDA = 97

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def revn(n):
	return str(n)[::-1]

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=2):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base):
	newnumber = 0
	while number > 0:
		newnumber += number % base
		number //= base
	return newnumber

def cdiv(n, k):
	return n // k + (n % k != 0)
(n, m) = mi()
s = list(input())
d = {chr(ORDA + i): chr(ORDA + i) for i in range(26)}
for i in range(m):
	(oldc, newc) = input().split()
	(d[oldc], d[newc]) = (d[newc], d[oldc])
rezd = {d[i]: i for i in d}
print(*[rezd[s[i]] for i in range(n)], sep='')


(n, m) = [int(i) for i in input().split()]
s = input()
st = [chr(ord('a') + i) for i in range(26)]
for i in range(m):
	(a, b) = input().split()
	for i in range(26):
		if st[i] == a:
			st[i] = b
		elif st[i] == b:
			st[i] = a
print(''.join([st[ord(i) - ord('a')] for i in s]))


from sys import *
input = stdin.readline
from string import ascii_lowercase as c
g = {}
(n, m) = map(int, input().split())
ans = [''] * n
s = input()
for i in c:
	g[i] = []
for i in range(n):
	g[s[i]] += [i]
for i in range(m):
	(a, b) = input().split()
	(g[a], g[b]) = (g[b], g[a])
for i in g:
	for j in g[i]:
		ans[j] = i
print(''.join(ans))


import sys
import string
lines = sys.stdin.readlines()
(m, n) = map(int, lines[0].split())
s = list(lines[1])
r = {c: c for c in string.ascii_lowercase}
for i in range(n):
	(x, y) = (lines[2 + i][0], lines[2 + i][2])
	for (a, b) in r.items():
		if b == x:
			r[a] = y
		elif b == y:
			r[a] = x
for i in range(m):
	s[i] = r[s[i]]
print(''.join(s))


(l, a) = map(int, input().split())
s = input()
replace = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for i in range(a):
	b = input().split()
	x = b[0]
	y = b[1]
	for j in range(26):
		if replace[j] == x:
			replace[j] = y
		elif replace[j] == y:
			replace[j] = x
output = ''
for i in range(l):
	output += replace[ord(s[i]) - 97]
print(output)


(letters, designers) = [int(x) for x in input().split(' ')]
name = input()
alphabet_dict = {x: x for x in range(26)}
alphabet_arr = [x + 97 for x in range(26)]

def print_dict(dict_al):
	for (key, value) in dict_al.items():
		print('{}: {}'.format(chr(key), chr(value)))
for _ in range(designers):
	(letter1, letter2) = input().split(' ')
	who_has_1 = alphabet_dict[ord(letter1) - 97]
	who_has_2 = alphabet_dict[ord(letter2) - 97]
	alphabet_arr[who_has_1] = ord(letter2)
	alphabet_arr[who_has_2] = ord(letter1)
	alphabet_dict[ord(letter1) - 97] = who_has_2
	alphabet_dict[ord(letter2) - 97] = who_has_1
for letter in name:
	print(chr(alphabet_arr[ord(letter) - 97]), end='')
print()


import string
n = int(input().split()[1])
s = list(input())
r = {c: c for c in string.ascii_lowercase}
for i in range(n):
	(x, y) = input().split()
	for (a, b) in r.items():
		if b == x:
			r[a] = y
		elif b == y:
			r[a] = x
for i in range(len(s)):
	s[i] = r[s[i]]
print(''.join(s))


(n, m) = input().split()
s = input()
n = int(n)
m = int(m)
l = [[] for i in range(26)]
for i in range(n):
	r = ord(s[i]) - 97
	l[r].append(i)
for i in range(m):
	(k1, k2) = input().split()
	(r1, r2) = (ord(k1) - 97, ord(k2) - 97)
	(l[r1], l[r2]) = (l[r2], l[r1])
q = [0 for i in range(n)]
for i in range(26):
	q1 = len(l[i])
	q2 = chr(97 + i)
	if q1 != 0:
		for j in range(q1):
			q[l[i][j]] = q2
for i in range(n):
	print(q[i], end='')


(n, m) = map(int, input().split())
s = input()
d = dict()
for i in range(26):
	d[chr(i + 97)] = chr(i + 97)
for i in range(m):
	(a, x) = input().split()
	for j in range(26):
		if d[chr(j + 97)] == a:
			d[chr(j + 97)] = x
		elif d[chr(j + 97)] == x:
			d[chr(j + 97)] = a
for i in s:
	print(d[i], end='')


def main():
	(_, m) = map(int, input().split())
	(s, d) = (input(), {c: c for c in 'abcdefghijklmnopqrstuvwxyz'})
	for _ in range(m):
		(x, y) = input().split()
		(d[x], d[y]) = (d[y], d[x])
	d = {v: k for (k, v) in d.items()}
	print(''.join((d[c] for c in s)))
main()


from collections import *
d = defaultdict(list)
(n, m) = map(int, input().split())
s = input()
l = 'abcdefghijklmnopqrstuvwxyz'
for i in l:
	d[i] = i
for i in range(m):
	(x, y) = input().split()
	for k in d.keys():
		if d[k] == x:
			d[k] = y
		elif d[k] == y:
			d[k] = x
for i in s:
	print(d[i], end='')
print()


import sys
(n, m) = [int(x) for x in input().split()]
s = input()
c1 = ord('a')
c2 = ord('z')
ma = [i for i in range(c2 - c1 + 1)]
where = [i for i in range(c2 - c1 + 1)]
for i in range(m):
	(cf, cs) = [ord(c) for c in input().split()]
	wcf = where[cf - c1]
	wcs = where[cs - c1]
	(ma[wcf], ma[wcs]) = (ma[wcs], ma[wcf])
	(where[cf - c1], where[cs - c1]) = (where[cs - c1], where[cf - c1])
ans = []
for c in s:
	cur = ord(c)
	ans.append(chr(ma[cur - c1] + c1))
print(''.join(ans))


(n, m) = map(int, input().split())
S = input()
l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
l1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for i in range(m):
	(a, b) = input().split()
	c = 0
	if a != b:
		p = l1.index(a)
		p1 = l1.index(b)
		l1[p] = b
		l1[p1] = a
S1 = ''
for i in range(len(S)):
	S1 = S1 + l1[l.index(S[i])]
print(S1)


(n, m) = map(int, input().split(' ')[:2])
s = input()[:n]
ls = {}
for c in range(97, 123):
	ls[chr(c)] = chr(c)
for i in range(m):
	(x, y) = input().split(' ')[:2]
	(ls[x], ls[y]) = (ls[y], ls[x])
rev = {}
for (c, v) in ls.items():
	rev[v] = c
print(''.join([rev[c] for c in s]))


(n, m) = map(int, input().split())
s = input()
perm = list(range(26))
v = ord('a')
for _ in range(m):
	ss = input()
	(i, j) = (ord(ss[0]) - v, ord(ss[2]) - v)
	(perm[i], perm[j]) = (perm[j], perm[i])
rev = [perm.index(c) for c in range(26)]
print(''.join((chr(rev[ord(c) - v] + v) for c in s)))


import string
t = string.ascii_lowercase
t2 = list(t)
(n, m) = map(int, input().split())
s = input()
for i in range(m):
	(x, y) = input().split()
	index_x = t2.index(x)
	index_y = t2.index(y)
	(t2[index_x], t2[index_y]) = (t2[index_y], t2[index_x])
for i in s:
	index = ord(i) - ord('a')
	print(t2[index], end='')


import sys
digitInput = sys.stdin.readline().split()
originalAlpha = 'abcdefghijklmnopqrstuvwxyz'
newAlpha = 'abcdefghijklmnopqrstuvwxyz'
word = sys.stdin.readline()
for n in range(int(digitInput[1])):
	change = sys.stdin.readline().strip('\n').split()
	newAlpha = newAlpha.replace(change[0], change[1].upper())
	newAlpha = newAlpha.replace(change[1], change[0])
	newAlpha = newAlpha.lower()
for f in range(26):
	word = word.replace(originalAlpha[f], newAlpha[f].upper())
sys.stdout.write(word.lower())


import string
(n, m) = [int(x) for x in input().split(' ')]
s = input()
xy = {}
for c in string.ascii_lowercase:
	xy[c] = c
for i in range(m):
	(x, y) = input().split(' ')
	x_ls = []
	y_ls = []
	for (k, v) in xy.items():
		if v == x:
			x_ls.append(k)
		if v == y:
			y_ls.append(k)
	for k in x_ls:
		xy[k] = y
	for k in y_ls:
		xy[k] = x
ans = ''
for c in s:
	ans += xy[c]
print(ans)


(n, m) = map(int, input().split())
s = input()
mp = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
mp2 = mp[:]
for i in range(m):
	(a, b) = input().split()
	t = mp2.index(a)
	mp2[mp2.index(b)] = a
	mp2[t] = b
x = list(s)
for i in range(n):
	x[i] = mp2[mp.index(x[i])]
print(''.join(x))


from sys import stdin
inp = stdin.readline().split()
m = int(inp[1])
word = stdin.readline().strip()
replaces = {}
for i in range(0, m):
	replacement = stdin.readline().split()
	fr = replacement[0]
	to = replacement[1]
	for (key, value) in replaces.items():
		if value == fr:
			replaces[key] = to
		if value == to:
			replaces[key] = fr
	if fr not in replaces:
		replaces[fr] = to
	if to not in replaces:
		replaces[to] = fr
table = str.maketrans(*[''.join(x) for x in zip(*replaces.items())])
word = word.translate(table)
print(word)


(n, m) = map(int, input().split())
s = input()
matrix = []
for r in range(26):
	matrix.append([0] * 26)
	matrix[-1][r] = 1
for _ in range(m):
	(old, new) = input().split()
	_old = ord(old) - ord('a')
	_new = ord(new) - ord('a')
	(matrix[_old], matrix[_new]) = (matrix[_new], matrix[_old])
ans = []
changes = {}
for (i, row) in enumerate(matrix):
	pos = row.index(1)
	changes[chr(pos + ord('a'))] = chr(i + ord('a'))
for c in s:
	ans.append(c if c not in changes else changes[c])
ans = ''.join(ans)
print(ans)


(n, m) = map(int, input().split())
s = input()
w = list(range(26))
for i in range(m):
	(a, b) = input().split()
	(c, d) = (ord(a) - ord('a'), ord(b) - ord('a'))
	(w[c], w[d]) = (w[d], w[c])
t = {chr(w[c] + ord('a')): chr(c + ord('a')) for c in range(26)}
for c in s:
	print(t[c], end='')
print()


(a, b) = map(int, input().split())
word = input()
changes = {chr(i): chr(i) for i in range(ord('a'), ord('z') + 1)}
actions = [tuple(input().split()) for i in range(b)]
for (fm, to) in reversed(actions):
	(changes[fm], changes[to]) = (changes[to], changes[fm])
for i in word:
	print(changes[i], end='')


def main():
	(n, m) = map(int, input().split())
	s = input()
	l = list('abcdefghijklmnopqrstuvwxyz')
	f = l.index
	for _ in range(m):
		(x, y) = map(f, input().split())
		(l[x], l[y]) = (l[y], l[x])
	print(''.join((l[ord(c) - 97] for c in s)))
main()


(n, m) = map(int, input().split())
original_name = input()
changes = [input().split() for _ in range(m)]
original_char_dict_list = sorted(list(set(original_name)))
modified_char_dict_list = sorted(list(set(original_name)))
for pair in changes:
	for (i, c) in enumerate(modified_char_dict_list):
		if c == pair[0]:
			modified_char_dict_list[i] = pair[1]
		elif c == pair[1]:
			modified_char_dict_list[i] = pair[0]
dictionary = {c: modified_char_dict_list[i] for (i, c) in enumerate(original_char_dict_list)}
name_list = list(original_name)
for (i, c) in enumerate(name_list):
	name_list[i] = dictionary[c]
print(''.join(name_list))


(n, m) = map(int, input().split())
s = list(input())
d_c = {}
for c in range(26):
	d_c[chr(ord('a') + c)] = chr(ord('a') + c)
for _ in range(m):
	(x, y) = input().split()
	if x != y:
		(d_c[x], d_c[y]) = (d_c[y], d_c[x])
d_c = {v: k for (k, v) in d_c.items()}
print(''.join((d_c[c] for c in s)))


import string
(n, m) = map(int, input().split())
name = input()
tr = string.ascii_lowercase
for _ in range(m):
	(src, dst) = input().split()
	tr = tr.replace(src, '@').replace(dst, src).replace('@', dst)
for c in name:
	pos = ord(c) - ord('a')
	print(tr[pos], end='')
print()


(a, b) = (int(i) for i in input().split())
import string
str = input()
g = {c: c for c in string.ascii_lowercase}
for j in range(b):
	(e, r) = (h for h in input().split())
	(g[e], g[r]) = (g[r], g[e])
g2 = {b: a for (a, b) in g.items()}
print(''.join((g2[c] for c in str)))


import string
(n, m) = map(int, input().split())
word = list(input())
alphabet = list(string.ascii_lowercase)
alphabet_dict = {}
for i in range(len(alphabet)):
	alphabet_dict[alphabet[i]] = alphabet[i]
for i in range(m):
	(x, y) = input().split()
	for letter in alphabet_dict:
		if alphabet_dict[letter] == x:
			alphabet_dict[letter] = y
		elif alphabet_dict[letter] == y:
			alphabet_dict[letter] = x
for i in range(len(word)):
	word[i] = alphabet_dict[word[i]]
print(''.join(word))


(n, m) = map(int, input().split())
name = input()
changes = [input().split() for i in range(m)]
changes_table = sorted(list(set(name)))
for (x, y) in changes:
	for (i, c) in enumerate(changes_table):
		if c == x:
			changes_table[i] = y
		elif c == y:
			changes_table[i] = x
lookup_table = {c: changes_table[i] for (i, c) in enumerate(sorted(list(set(name))))}
final_name = ''.join(map(lambda c: lookup_table[c], name))
print(final_name)


(n, m) = map(int, input().split())
st = input()
dic = {}
xr = 'abcdefghijklmnopqrstuvwxyz'
for x in xr:
	dic[x] = x
for x in range(m):
	(g, h) = input().split()
	(dic[g], dic[h]) = (dic[h], dic[g])
t = {}
for k in dic:
	t[dic[k]] = k
ls = [t[x] for x in st]
print(''.join(ls))


import math, itertools, fractions, heapq, collections, bisect, sys, queue, copy
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

def S():
	return input()
alf = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

def main():
	(n, k) = LI()
	d = {}
	for x in alf:
		d[x] = x
	s = S()
	for _ in range(k):
		(a, b) = LS()
		for (k, v) in d.items():
			if v == a:
				d[k] = b
			if v == b:
				d[k] = a
	ans = ''
	for x in s:
		ans += d[x]
	return ans
print(main())


inp = input().strip().split()
(n, m) = (int(inp[0]), int(inp[1]))
s = input().strip()
d = {}
for i in range(n):
	if s[i] in d:
		d[s[i]].append(i)
	else:
		d[s[i]] = [i]
for i in range(m):
	inp = input().strip().split()
	(l0, l1) = ([], [])
	(b0, b1) = (False, False)
	if inp[0] in d:
		b0 = True
	if inp[1] in d:
		b1 = True
	if b0 and b1:
		(d[inp[0]], d[inp[1]]) = (d[inp[1]], d[inp[0]])
	elif b0 and (not b1):
		d[inp[1]] = d[inp[0]]
		del d[inp[0]]
	elif b1 and (not b0):
		d[inp[0]] = d[inp[1]]
		del d[inp[1]]
ans = [0] * n
for key in d.keys():
	for i in d[key]:
		ans[i] = key
for ctmp in ans:
	print(ctmp, end='')
print()


(n, m) = map(int, input().split())
s = input()
d = {}
for i in 'abcdefghijklmnopqrstuvwxyz':
	d[i] = []
for (j, l) in enumerate(s):
	d[l].append(j)
for i in range(m):
	(xi, yi) = input().split()
	(d[xi], d[yi]) = (d[yi], d[xi])
r = {}
for (k, v) in d.items():
	for pos in v:
		r[pos] = k
for l in sorted(r.items()):
	print(l[1], end='')


from collections import defaultdict

def rebranding():
	n_m = input().split()
	n = int(n_m[0])
	m = int(n_m[1])
	brand_name = list(input())
	lowercase_letters = list(map(chr, range(97, 123)))
	origin_lowercase_letters = list(map(chr, range(97, 123)))
	for _ in range(0, m):
		(x, y) = input().split()
		if x != y:
			idx = lowercase_letters.index(x)
			idy = lowercase_letters.index(y)
			lowercase_letters[idx] = y
			lowercase_letters[idy] = x
	dictionnary = defaultdict(str)
	for (i, letter) in enumerate(origin_lowercase_letters):
		dictionnary[letter] = lowercase_letters[i]
	for (i, letter) in enumerate(brand_name):
		brand_name[i] = dictionnary[letter]
	print(''.join(brand_name))
rebranding()


(n, m) = map(int, input().split())
l = list(input())
alpha = [chr(i) for i in range(97, 123)]
for i in range(m):
	(ch1, ch2) = input().split()
	ord1 = alpha.index(ch1)
	ord2 = alpha.index(ch2)
	(alpha[ord1], alpha[ord2]) = (alpha[ord2], alpha[ord1])
for i in range(n):
	o = ord(l[i]) - 97
	l[i] = alpha[o]
print(''.join(l))


(n, m) = map(int, input().split())
s = str(input())
old = 'abcdefghijklmnopqrstuvwxyz'
new = old
for _ in range(m):
	(x, y) = input().split()
	new = new.translate(''.maketrans(x + y, y + x))
print(s.translate(''.maketrans(old, new)))


def get_ord(x):
	return ord(x) - ord('a')
(length, query) = [int(i) for i in input().split()]
line = input()
lst = [list() for i in range(26)]
for i in range(length):
	lst[get_ord(line[i])].append(i)
for loop in range(query):
	(x, y) = input().split()
	(lst[get_ord(x)], lst[get_ord(y)]) = (lst[get_ord(y)], lst[get_ord(x)])
ans = [0] * length
for i in range(26):
	for pos in lst[i]:
		ans[pos] = chr(i + ord('a'))
print(''.join(ans))


def tr(d, a, b):
	for (i, j) in d.items():
		if j == a:
			d[i] = b
		elif j == b:
			d[i] = a
	if not a in d.keys():
		d.update({a: b})
	if not b in d.keys():
		d.update({b: a})
m = int(input().split()[1])
name = input()
s = set(name)
d = dict()
for i in range(m):
	(a, b) = input().split()
	if a != b:
		tr(d, a, b)
name = name.translate(str.maketrans(''.join(d.keys()), ''.join(d.values())))
print(name)


import string
import sys

def solve(s, pairs):
	origin_of = {c: c for c in string.ascii_lowercase}
	for (c1, c2) in pairs:
		(origin_of[c1], origin_of[c2]) = (origin_of[c2], origin_of[c1])
	d = {v: k for (k, v) in origin_of.items()}
	return ''.join((d[c] for c in s))

def solve0(s, pairs):
	d = {c: c for c in string.ascii_lowercase}
	for (c1, c2) in pairs:
		for c in string.ascii_lowercase:
			if d[c] == c1:
				d[c] = c2
			elif d[c] == c2:
				d[c] = c1
	return ''.join((d[c] for c in s))

def main():
	[n, m] = [int(i) for i in input().strip().split()]
	s = input().strip()
	assert len(s) == n
	pairs = [tuple(input().strip().split()) for _ in range(m)]
	result = solve(s, pairs)
	print(result)
main()


from sys import *
from collections import Counter, defaultdict
input = stdin.readline
listInput = lambda : list(map(int, input().strip().split()))
lineInput = lambda : map(int, input().strip().split())

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(math.sqrt(n) + 1), 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def main():
	(n, m) = lineInput()
	s = list(input().strip())
	ans = ''
	alpa = 'abcdefghijklmnopqrstuvwxyz'
	dic = defaultdict(list)
	for i in alpa:
		dic[i] = i
	for _ in range(m):
		(x, y) = map(str, input().strip().split(' '))
		for v in dic.keys():
			if dic[v] == x:
				dic[v] = y
			elif dic[v] == y:
				dic[v] = x
	for i in s:
		print(dic[i], end='')
	print()
main()


(n, m) = map(int, input().split())
x = list(input())
d = {}
y = list(set(x))
z = list(set(x))
for i in x:
	d[i] = i
for t in range(m):
	(a, b) = map(str, input().split())
	for i in range(len(y)):
		if y[i] == a:
			y[i] = b
		elif y[i] == b:
			y[i] = a
for i in range(len(y)):
	d[z[i]] = y[i]
for i in range(n):
	x[i] = d[x[i]]
print(''.join(x))


import sys
(n, m) = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().strip()

def replaceRequests(n, m, s):
	alph = ''
	for code in range(ord('a'), ord('z') + 1):
		alph = alph + chr(code)
	english_alph = alph
	alph = list(alph)
	for t in range(m):
		request = sys.stdin.readline().strip().split()
		index1 = alph.index(request[0])
		index2 = alph.index(request[1])
		(alph[index1], alph[index2]) = (alph[index2], alph[index1])
	alph_replace = {}
	for pos in range(len(alph)):
		alph_replace[english_alph[pos]] = alph[pos]
	replacedS = list(s)
	for pos in range(len(s)):
		replacedS[pos] = alph_replace[replacedS[pos]]
	return ''.join(replacedS)
print(replaceRequests(n, m, s))


from sys import *
from collections import *

def inp(n):
	if n == 1:
		return map(int, stdin.readline().split())
	elif n == 2:
		return map(float, stdin.readline().split())
	else:
		return map(str, stdin.readline().split())

def main():
	(n, m) = inp(1)
	(org, mem) = (deque(input()), defaultdict(int))
	for i in range(m):
		(u, v) = inp(3)
		(flag1, flag2) = (0, 0)
		for (i, j) in mem.items():
			if not flag1 and j == u:
				mem[i] = v
				flag1 = 1
			if not flag2 and j == v:
				mem[i] = u
				flag2 = 1
			if flag1 and flag2:
				break
		if not flag1:
			mem[u] = v
		if not flag2:
			mem[v] = u
	for i in range(n):
		if mem[org[i]]:
			org[i] = mem[org[i]]
	print(''.join(org))
main()


def solve():
	s = 'abcdefghijklmnopqrstuvwxyz'
	d = {i: i for i in s}
	(n, m) = map(int, input().split())
	inp = input()
	for i in range(m):
		(x, y) = input().split()
		for k in d.keys():
			if d[k] == x:
				d[k] = y
			elif d[k] == y:
				d[k] = x
	inp = list(inp)
	for (idx, i) in enumerate(inp):
		inp[idx] = d[i]
	print(''.join(inp))
solve()


import string
(n, m) = map(int, input().split())
s = input()
sample = string.ascii_lowercase
for _ in range(m):
	(x, y) = input().split()
	sample = sample.translate(str.maketrans(x + y, y + x))
print(s.translate(str.maketrans(string.ascii_lowercase, sample)))


alf = [''] * 26
for i in range(26):
	alf[i] = chr(97 + i)
l = list(map(int, input().split()))
(n, m) = (l[0], l[1])
s = input()
for i in range(m):
	z = list(input().split())
	(x, y) = (z[0], z[1])
	for i in range(26):
		if alf[i] == x:
			alf[i] = y
		elif alf[i] == y:
			alf[i] = x
ans = ''
for j in range(n):
	ans += alf[ord(s[j]) - 97]
print(ans)


(n, m) = map(int, input().split())
name = input()
charList = [[chr(ord('a') + i), chr(ord('a') + i)] for i in range(26)]
for i in range(m):
	(x, y) = input().split()
	(charList[ord(y) - ord('a')][1], charList[ord(x) - ord('a')][1]) = (charList[ord(x) - ord('a')][1], charList[ord(y) - ord('a')][1])
	(charList[ord(y) - ord('a')], charList[ord(x) - ord('a')]) = (charList[ord(x) - ord('a')], charList[ord(y) - ord('a')])
charList.sort()
newName = ''
for i in range(n):
	newName = newName + charList[ord(name[i]) - ord('a')][1]
print(newName)


import math as mt
import sys, string, bisect
input = sys.stdin.readline
import random
from collections import deque, defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
d = defaultdict(list)
(n, m) = M()
s = input().strip()
w = 'abcdefghijklmnopqrstuvwxyz'
for i in w:
	d[i] = i
for _ in range(m):
	(a, b) = input().split()
	c = 0
	for i in d.keys():
		if d[i] == a:
			d[i] = b
		elif d[i] == b:
			d[i] = a
for i in s:
	print(d[i], end='')


import sys
import itertools
import math
import collections
from collections import Counter

def getdict(n):
	d = {}
	if type(n) is list:
		for i in n:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	else:
		for i in range(n):
			t = ii()
			if t in d:
				d[t] += 1
			else:
				d[t] = 1
	return d

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = prime[1] = False
	r = [p for p in range(n + 1) if prime[p]]
	return r

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return collections.defaultdict(int)
(n, m) = mi()
s = [x for x in input()]
d = {chr(ord('a') + i): chr(ord('a') + i) for i in range(26)}
for _ in range(m):
	(a, b) = input().split()
	(d[a], d[b]) = (d[b], d[a])
r = {d[i]: i for i in d}
prr([r[s[i]] for i in range(n)], '')