Олимпиадный тренинг

Задача . A. Ярмарка в Скарборо

Задача

Темы: реализация *800

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, c₁, c₂, означающими, что все символы c₁ на промежутке [l, r] (от l-го до r-го, включая l и r) должны быть заменены на c₂. Строка индексируется начиная с 1.

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

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

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

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

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