E. Меняем строку
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$, которая состоит только из трех первых букв латинского алфавита, то есть каждый символ строки — a, b или c.

Также даны $$$q$$$ операций, которые необходимо совершить над строкой. В каждой операции даны две буквы $$$x$$$ и $$$y$$$ из множества трех первых букв латинского алфавита, и для каждой операции нужно совершить одно из следующих двух действий:

  • изменить в строке $$$s$$$ одно любое вхождение буквы $$$x$$$ на букву $$$y$$$ (если хотя бы одно вхождение буквы $$$x$$$ есть);
  • ничего не делать.

Требуется совершить все операции в заданном порядке таким образом, чтобы строка $$$s$$$ стала лексикографически минимальной.

Напоминаем, что строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:

  • $$$a$$$ — префикс $$$b$$$, но $$$a \neq b$$$;
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^{3}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных находятся два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^{5}$$$) — длина строки $$$s$$$ и количество операций.

Во второй строке каждого набора входных данных задана $$$s$$$ — строка из ровно $$$n$$$ символов, каждый из которых — a, b или c.

Следующие $$$q$$$ строк каждого набора входных данных содержат описание операций. Каждая строка содержит два символа $$$x$$$ и $$$y$$$, каждый из которых — a, b или c.

Дополнительные ограничения на входные данные:

  • сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^{5}$$$;
  • сумма $$$q$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^{5}$$$.
Выходные данные

Для каждого набора входных данных выведите лексикографически минимальную строку, которую можно получить из $$$s$$$ данными операциями.

Пример
Входные данные
3
2 2
cb
c b
b a
10 10
bbbbbbbbbb
b a
b c
c b
b a
c a
b c
b c
b a
a b
c a
30 20
abcaababcbbcabcbbcabcbabbbbabc
b c
b c
c a
b c
b c
b a
b c
b c
b a
b a
b a
b a
c a
b c
c a
b c
c a
c a
b c
c b
Выходные данные
ab
aaaaabbbbb
aaaaaaaaaaaaaaabbbabcbabbbbabc
Примечание

В первом наборе входных данных обе операции нужно применить к первой букве:

  1. после первой операции $$$s = $$$ «bb»
  2. после второй операции $$$s = $$$ «ab»

Во втором наборе входных данных строка могла изменяться так:

  1. «bbbbabbbbb» (изменили $$$5$$$-ю букву)
  2. «cbbbabbbbb» (изменили $$$1$$$-ю букву)
  3. «cbbbabbbbb» (ничего не делали)
  4. «cbbaabbbbb» (изменили $$$4$$$-ю букву)
  5. «abbaabbbbb» (изменили $$$1$$$-ю букву)
  6. «abcaabbbbb» (изменили $$$3$$$-ю букву)
  7. «abcaabbbbb» (ничего не делали)
  8. «aacaabbbbb» (изменили $$$2$$$-ю букву)
  9. «aacaabbbbb» (ничего не делали)
  10. «aaaaabbbbb» (изменили $$$3$$$-ю букву)