威廉正带着女孩前往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。