Codeforces 591 B Rebranding【Codeforces Round #327 (Div. 2)】-白红宇

The name of one small but proud corporation consists of n lowercase English letters. The Corporation has decided to try rebranding — an active marketing strategy, that includes a set of measures to change either the brand (both for the company and the goods it produces) or its components: the name, the logo, the slogan. They decided to start with the name.

For this purpose the corporation has consecutively hired m designers. Once a company hires the i-th designer, he immediately contributes to the creation of a new corporation name as follows: he takes the newest version of the name and replaces all the letters x_i by y_i, and all the letters y_i by x_i. This results in the new version. It is possible that some of these letters do no occur in the string. It may also happen that x_i coincides with y_i. The version of the name received after the work of the last designer becomes the new name of the corporation.

Manager Arkady has recently got a job in this company, but is already soaked in the spirit of teamwork and is very worried about the success of the rebranding. Naturally, he can't wait to find out what is the new name the Corporation will receive.

Satisfy Arkady's curiosity and tell him the final version of the name.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the length of the initial name and the number of designers hired, respectively.

The second line consists of n lowercase English letters and represents the original name of the corporation.

Next m lines contain the descriptions of the designers' actions: the i-th of them contains two space-separated lowercase English letters x_i and y_i.

Output

Print the new name of the corporation.

Sample test(s)

Input

6 1policep m

Output

molice

Input

11 6abacabadabaa bb ca de gf ab b

Output

cdcbcdcfcdc

Note

In the second sample the name of the corporation consecutively changes as follows:

$\text{[math]}$

题目大意：

首先给定两个数 m, n 和一个字符串，m : 字符串的长度，n：表示有 n 行，

然后有两个字符 s ,t ，表示可以将字符s 转化为 t。也可以将字符t 转化为 s，

求最后转化后的字符串并输出。。。

解题思路：

首先将26个英文小写字母用一个数组a【】表示，下标为其所代表的ASCII码，

然后只需要从字符串 a 循环到 z就行了，如果遇到s 和 t就直接代替，并且将a【】数组中的 s 所对应的ASCII码

改为 t代表的就行了。。

上代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;#define MM(a) memset(a,0,sizeof(a))typedef long long LL;typedef unsigned long long ULL;const int maxn = 2*1e5+5;const int mod = 1000000007;const double eps = 1e0-7;char arr[maxn];char a[300];void Init(){ for(char i='a'; i<='z'; i++) a[(int)i] = i;}int main(){ int m, n; cin>>m>>n>>arr; Init(); while(n--) { char s, t; cin>>s>>t; for(char i='a'; i<='z'; i++) { if(s == a[(int)i]) a[(int)i] = t; else if(t ==a[(int)i]) a[(int)i] = s; } } for(int i=0; i