Задача №113352. Ребрендинг

Название одной маленькой, но очень гордой корпорации состоит из n строчных английских букв. Корпорация решила провести ребрендинг — активную маркетинговую стратегию, включающую комплекс мероприятий по изменению бренда (как компании, так и производимого ею товара), либо его составляющих: названия, логотипа, слогана. Начать решили именно с названия.

Для этого корпорация последовательно наняла \(m\) дизайнеров. Как только компания нанимает \(i\)-го дизайнера, тот сразу вносит свою лепту в создание нового имени корпорации следующим образом: он меняет в текущей версии названия все буквы \(x_i\) на \(y_i\) , а все буквы \(y_i\) на \(x_i\), после чего получается новая версия. Возможно, каких-то из этих букв в строке нет, а также возможно, что \(x_i\) совпадает с \(y_i\). Вариант имени, получившийся после работы последнего дизайнера, становится новым названием корпорации.

Менеджер Аркадий лишь недавно устроился на работу в эту фирму, но уже проникся корпоративным духом и очень переживает за успех ребрендинга. Естественно, ему не терпится узнать, какое имя в итоге получит корпорация.

Удовлетворите любопытство Аркадия — назовите ему окончательный вариант названия.

Входные данные

В первой строке входных данных находятся два числа \(n\) и \(m (1 ⩽ n, m ⩽ 200 000)\) — длина изначального названия и количество нанятых дизайнеров соответственно.

Вторая строка состоит из n строчных английских букв и представляет собой изначальное имя корпорации.

В следующих \(m\) строках содержатся описания действий дизайнеров: в \(i\)-й из последующих строк записаны две строчные английские буквы \(x_i\) и \(y_i\).

Выходные данные

Выведите окончательный вариант названия корпорации.

Примечание

Во втором примере название корпорации последовательно претерпевает следующие изменения:

abacabadaba → babcbabdbab

babcbabdbab → cacbcacdcac

cacbcacdcac → cdcbcdcacdc

cdcbcdcacdc → cdcbcdcacdc

cdcbcdcacdc → cdcbcdcfcdc

cdcbcdcfcdc → cdcbcdcfcdc

Примеры
Входные данные
6 1
police
p m
Выходные данные
molice
Входные данные
11 6
abacabadaba
a b
b c
a d
e g
f a
b b
Выходные данные
cdcbcdcfcdc
Сдать: для сдачи задач необходимо войти в систему