← 返回题目列表

Codeforces · 897/A

A. 斯卡伯勒集市

中文机器翻译题面 查看原题

威廉正带着女孩前往28号岛最高的建筑,然而他们都不知道怎么去那里。

威廉向他的朋友格里克问路,格里克帮助了他们,并给了他们一个任务。

虽然女孩想帮忙,但威廉坚持自己做。

格里克给了威廉一个长度为n的字符串。

Willem需要进行m次操作,每个操作有四个参数l、r、c1、c2,这意味着将[l,r]范围内的所有符号c1(从第l到第r,包括l和r)都变成c2。字符串的索引为 1。

Grick 想知道所有 m 次操作后的最终字符串。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100)。

第二行包含一个长度为n的字符串s,由小写英文字母组成。

接下来的 m 行每行包含四个参数 l、r、c1、c2(1 ≤ l ≤ r ≤ n,c1、c2 为小写英文字母),以空格分隔。

输出

执行上述m次操作后输出字符串s。

示例

输入 #1

3 1
ioi
1 1 i n

输出 #1

noi

输入 #2

5 3
wxhak
3 3 h x
1 5 x a
1 3 w g

输出 #2

gaaak

注意

对于第二个示例:

第一次操作后,字符串为wxxak。

第二次操作后,字符串为waaak。

第三次操作后,字符串为gaaak。