Description

输入一个字符串，以及若干次替换，请输出替换后的字符串。

Input

输入数据第一行是两个整数 $n,m(1≤n≤10^5,1≤m ≤10^5)$, 表示字符串的长度以及修改的次数，第二行是长度为 $n$ 的字符串，接下来 $m$ 行每行一个整数 $x(1≤x≤n)$ 和一个字符 $c$，分别表示修改的位置以及修改后的字符。保证输入的字符串及字符只包含大小写字母。

Output

输出一行表示修改后的字符串。

Samples

5 2
abcde
3 C
1 z

zbCde

5 2
abcde
3 C
3 z

abzde