A. Ярмарка в Скарборо
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Are you going to Scarborough Fair?

Parsley, sage, rosemary and thyme.

Remember me to one who lives there.

He once was the true love of mine.

Уильям хочет отвести подругу к самому высокому зданию на острове 28, однако никто из них не знает, как туда пройти.

Уильям просит своего друга, Грика, подсказать, как туда дойти. Грик помогает ребятам и даёт им задание.

Несмотря на то, что подруга Уильяма хочет помочь, Уильям решает справиться с ним самостоятельно.

Грик даёт Уильяму строку длины n.

Уильяму необходимо произвести m операций, каждая из которых описывается четырьмя параметрами l, r, c1, c2, означающими, что все символы c1 на промежутке [l, r] (от l-го до r-го, включая l и r) должны быть заменены на c2. Строка индексируется начиная с 1.

Грику необходимо узнать строку после всех m операций.

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

В первой строке содержатся два целых числа n и m (1 ≤ n, m ≤ 100).

Во втрой строке содержится строка s длины n, состоящая из строчных букв латинского алфавита.

В каждой из последующих m строк содержатся описания операций. Каждая операция задаётся четырьмя параметрами l, r, c1, c2 (1 ≤ l ≤ r ≤ n, c1, c2 являются строчными буквами латинского алфавита), разделёнными пробелами.

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

Выведите строку s после применения всех m операций, описанных выше.

Примеры
Входные данные
3 1
ioi
1 1 i n
Выходные данные
noi
Входные данные
5 3
wxhak
3 3 h x
1 5 x a
1 3 w g
Выходные данные
gaaak
Примечание

Во втором тестовом примере:

После применения первой операции строка становится равной wxxak.

После применения второй операции строка становится равной waaak.

После применения третьей операции строка становится равной gaaak.