虽然女孩想帮忙,但威廉坚持自己做。Grick给了Willem一个长度为n的字符串,Willem需要做m个运算,每个运算有四个参数l, r, c1, c2,这意味着[l, r]范围内的所有符号c1(从l-th到r-th,包括l和r)都变成了c2。字符串是1-indexed。Grick想知道所有m操作之后的最终字符串。
第一行包含两个整数n和m(1≤n, m≤100)。
第二行包含一个长度为n的字符串s,由小写的英文字母组成。
接下来的m行每一行包含4个参数l, r, c1, c2(1≤l≤r≤n, c1, c2为小写英文字母),用空格隔开。
执行上述m个操作后输出字符串s。
例子
Examples
Input
3 1
ioi
1 1 i n
Output
noi
Input
5 3
wxhak
3 3 h x
1 5 x a
1 3 w g
Output
gaaak
对于第二个例子:
在第一次操作之后,字符串是wxxak。
在第二次操作之后,字符串是waaak。
第三次操作后,字符串是gaaak。
慕仙8527320
慕神7151204
慕神7151204
慕斯4360584
慕斯4360584
慕斯4360584
慕慕5436299
慕慕5436299
相关分类