Задача №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