Problem: 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 xi by yi, and all the letters yi by xi. 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 xi coincides with yi. 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 xi and yi.

Output

Print the new name of the corporation.

Examples

Input

6 1
police
p m


Output

molice


Input

11 6
abacabadaba
a b
b c
a d
e g
f a
b b


Output

cdcbcdcfcdc

Note

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

<image>

<image>

<image>

<image>

<image>

<image>

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;


public class CodeForces {

    
    private static boolean sameset(int a, int b, int[] uf) {
        
        return find(a,uf) == find(b,uf);
    }

    private static void union(int a, int b, int[] uf) {
        uf[find(a,uf)] = find(b,uf);
    }

    private static int find(int a, int[] uf) {
        if(a == uf[a])  return a;
        int root = find(uf[a],uf);
        uf[a] = root;
        return root;
    }

    private static void BFS(int i, int[][] G, int[][] path) {
       // System.out.println("source vertex "+i);
        int[] v = new int[G.length]; // current maximum dist in u---v path
        ArrayDeque<Integer> A = new ArrayDeque();
        A.add(i);
        while(A.isEmpty() == false){
            int u = A.pop();
            //System.out.println("for node "+u);
            for(int a=0;a<v.length;a++){
                if(G[u][a] > 0 && v[a]==0 && a!=i){//edge in MST, later make faster
                    //System.out.println(a+" is and edge from "+u);
                    if(G[u][a] > v[u]){
                        //System.out.println(" and it incrases the sub path max ");
                        v[a] = G[u][a];
                    }
                    else    v[a] = v[u];
                    path[i][a] = v[a];
                    path[a][i] = v[a];
                   // System.out.println("finally path from "+i+" to "+a+" is "+path[i][a]);
                    
                    A.add(a);
                }
            }
        }
    }

    private static int numd(int x) {
        Double xx = Double.parseDouble(String.valueOf(x));
        int y = (int) Math.log10(xx);
        return (y+1);
       
         
        
    }

    private static String primeFactor(int n, boolean[] x) {
        String ans = "";
        for(int i=2;i<x.length;i++){
            if(i*i > n) break;
            if(x[i]){
                //System.out.println("testing prome "+i);
                while(n!=1 && i*i <= n){
                    while(n%i==0){
                       // System.out.println(i+" can divide "+n);
                        if(ans.equals(""))  ans=String.valueOf(i);
                        else    ans+=" x "+i;
                        n/=i;
                    }
                    break;
                }
            }
        }
        if(n!=1){
           // System.out.println("Remainig "+n);
            if(ans.equals(""))  ans=String.valueOf(n);
            else    ans+=" x "+n;
        }
        return ans;
    }

    private static String solve(String s) {
        
        
        
        return null;
    }

    //counts the number of divisors using the fundamental theorem of arithmetic
    private static int getDivisorCount(int n) {
        
        int count = 1;
        
        int tmp = n;
        
        for(int i=2;i*i<=n;i=(i==2?3:i+2)){
            
            //System.out.println(i+" is odd");
            
            int pow = 0;
            
            while(n%i==0){
                pow+=1;
                n/=i;
            }
            
            if(pow != 0){
                ///System.out.println(i+" must be a prime");
                count*=(pow+1);
            }
        }
        
        if(n!=1){
            //System.out.println(n+" is the last prime factor");
            count*=2;
        }
        
        //System.out.println("number of divisors of "+tmp+" is "+count);
        return count;
    }

    private static long nchoosek(int n, int k) {
        
        long prod = 1;
        int j = 1;
        
        int st = Math.max(n-k, k)+1;
        int ed = Math.min(n-k, k);
        
        for(int i=st;i<=n;i++){
            for(;j<=ed;j++){
                if(prod%j==0)   prod/=j;
                else break;
            }
            prod*=i;
        }
        
        for(;j<=ed;j++){
            prod/=j;
        }
        
        return prod;
    }
    
    //related to extgcd problems
    private static boolean check() {
        //System.out.println(a+" "+b+" "+c1+" "+c2);
        if(n%ibgcd(a,b)!=0) {
           // System.out.println("not possible");
            return false;
        }
        
        extgcd(a,b);
        long gcd=0,m1=x,m2=y;
        gcd=d;
        m1*=(n/d);
        m2*=(n/d);
        a/=d;
        b/=d;
        
        double f1 = (m1/b);f1*=-1;
        double f2 = (m2/a);
        long le = (long) Math.ceil(f1);
        long re = (long) Math.floor(f2);
        if(le > re) return false;
        long cf=c1*b-c2*a;
        if(cf*le < cf*re){
        
            x = m1+b*le;
            y = m2-a*le;
        }else{
            x = m1+b*re;
            y = m2-a*re;
        }
        //System.out.println("upper and lower are "+le+" "+re);
        
        
        return true;
    }

    private static void extgcd(long a, long b) {
        
        if(b==0){
            x=1;y=0;d=a;return;
        }
        extgcd(b,a%b);
        long x1 = y;
        long y1 = x-(a/b)*y;
        x=x1;
        y=y1;
    }

    private static void floyd_cycle(int z, int I, int m, int x0) {
        
        int tor = func(z,I,m,x0);
        int har = func(z,I,m,tor); //one step ahead of tor
        //System.out.println("initial value for tor and har "+tor+" "+har);
        
        while(tor!=har){
            tor = func(z,I,m,tor);
            har = func(z,I,m,har);
            har = func(z,I,m,har);
            //System.out.println("tor and har "+tor+" "+har);
        }
        
        //at r-x%m now
        int x = 0;
        har = tor;
        tor = x0;
        
        while(har!=tor){
            
            tor = func(z,I,m,tor);
            har = func(z,I,m,har);
            x+=1;
            //System.out.println("findind x tor and har "+tor+" "+har);
        }
        
        //now at first reapting node
        int lam = 1;
        har = func(z,I,m,tor);
        
        while(har!=tor){
            har = func(z,I,m,har);
            lam+=1;
            //System.out.println("finding lam, tor and har "+tor+" "+har);
        }
        
       // return new Pair(z,lam);
    }

   private static int func(int z, int I, int m, int x0) {
        return ((z*x0)%m+I%m)%m;
    }

    private static void dfs(int a, int[][] d, int[] v,int[] p) {
        
        v[a] = 1;
        for(int i=0;i<v.length;i++){
            if(i!=a && d[i][a]!=0){
                if(v[i]==0){
                   // System.out.println("dfsing "+i);
                    p[i]=a;
                    dfs(i,d,v,p);
                }else if(p[a] != i && a<i){
                   // System.out.println(a+" and "+i+" causing cycle"+p[i]);
                    cycle=true;
                }
            }
        }
        
    }

    private static void dolve(int x, int[] a) {
        //find sors of x
        int cnt = 0;
        for(int i=2;i<=Math.sqrt(x);i=(i==2?3:i+2)){
            int pow = 0;
            while(x%i==0){
                x/=i;
                pow+=1;
            }
            if(pow!=0){
                for(int j=1;j<=pow;j++){
                    long f = (long) Math.pow(i, j);
                    
                    if(f<a.length){
                        a[Integer.parseInt(String.valueOf(f))]=1;
                        //System.out.println("ading "+Integer.parseInt(String.valueOf(f)));
                    }
                    
                }
            }
        }
        
        if(x!=1){
            //System.out.println("ading "+x);
            if(x<a.length)  a[x]=1;
        }
    }

    

    private static long search(long max, long tmp, long a, long b) {
        
        long lo = 0;
        long hi = max;
        
        while(lo < hi){
            
            long mid = (lo+hi)>>1;
            
            long k = mid*a;
            k/=b;
            if(k==tmp)  hi=mid;
            else    lo = mid+1;
        }
        
        return lo;
    }

    

    private static int palindrome(int i, int j, String s, int[][] dp) {
        //if(i > j)   System.out.println("PLEASE STOP");
        int ret = 0;
        if(i==j)    {
            dp[i][j]=ret;
            return ret;
        }
        if(i+1==j && s.charAt(i)==s.charAt(j))  {
            dp[i][j]=ret;
            return ret;
        }
        if(i+1==j && s.charAt(i)!=s.charAt(j))  {
            
            ret = 1;
            dp[i][j]=ret;
            return ret;
        }
        
        if(s.charAt(i) == s.charAt(j)){
            
            ret = dp[i+1][j-1]==-1 ? palindrome(i+1,j-1,s,dp) : dp[i+1][j-1];
            //ret = 2+ sub;
            dp[i][j]=ret;
            return ret;
        }
        else{
            int sub1 = dp[i+1][j]==-1 ? palindrome(i+1,j,s,dp) : dp[i+1][j];
            int sub2 = dp[i][j-1]==-1 ? palindrome(i, j-1,s,dp) : dp[i][j-1];
            int sub3 = dp[i+1][j-1]==-1 ? palindrome(i+1,j-1,s,dp) : dp[i+1][j-1];
            
            ret = Math.min(sub1, sub2);
            ret = Math.min(ret, sub3);
            ret+=1;
            dp[i][j]=ret;
            return ret;
        }
        //return 0;
    }

    private static ArrayList<Integer> dfs_p(int a, int[] v, int[][] g, ArrayList<Integer> A) {
        
        v[a]=1;
        A.add(a);
        
        for(int i=0;i<v.length;i++){
            if(i!=a){
                if(g[a][i]==1 && v[i]==0){
                    //System.out.println("picking "+i);
                    return dfs_p(i, v, g, A);
                }
            }
        }
        return A;
        
    }

    private static double qs(double lo, double hi, Pair[] S) {
        
        double ans = -1.0;
        
        for(int i=0;i<1000;i++){
            double mid = (lo+hi)/2.0;
            //System.out.println("using a radius of "+mid);
            ans=mid;
            long tmp = 0;
            for(int j=0;j<S.length;j++){
                if(mid < S[j].d)    break;
                else{
                    tmp+=Long.parseLong(String.valueOf(S[j].p));
                }
            }
            //System.out.println("pop is "+tmp);
            
            if(tmp >= 1000000){
                hi=mid;
            }
            else if(tmp < 1000000){
                lo=mid;
            }
            
        }
        
       // System.out.println("usig ans os "+ans);
        //check again
        long tmp = 0;
        for(int i=0;i<S.length;i++){
            double d = Double.parseDouble(String.format( "%.7f", S[i].d ));
            ans = Double.parseDouble(String.format( "%.7f", ans ));
            //System.out.println(d+" "+ans);
            if(d > ans)    break;
            else{
                tmp += S[i].p;
            }
        }
        
        if(tmp >= 1000000)  return ans;
        
        
        
        return -1.0;
    }

   

    static class Node{
        
        int d=-1;
        long num;
        public Node(int a,long c){
            this.d = a;
            
            this.num = c;
            
        }
    }
    
    static class Edge{
        
        String d;
        int p;//ids of nodes
        int q;
        public Edge( String x1, int y1, int w){
            
            this.d = x1;
            this.p = y1;
            this.q = w;
        }
    }
    
    //simple sieve
    static boolean[] getPrimes(int n){
        
        boolean[] ret = new boolean[n+1];
        Arrays.fill(ret, true);
        
        ret[0] = ret[1] = false;
        
        for(int i=2;i*i <= n; i++){
            
            if(ret[i]){
                
                for(int j=i*i;j<=n;j+=i){
                    
                    ret[j]=false;
                }
            }
        }
        
        return ret;
    }
   
    static long ibgcd(long a, long b){
        
        while(b > 0){
            long r = a%b;
            a=b;
            b=r;
        }
        return a;
    }
    
    //for extgcd
    static long x,y,d; //output and gdc
    static long c1,c2,a,b,n; // inputs
    //static boolean[] p = getPrimes(5000001);
    
    static class Pair{
        double d ;
        int x;
        int y;
        int p;
        public Pair(int a, int f, int p){
            this.x = a;
            this.y = f;
            this.p=p;
            //compute the radius or euclidean distance
            double r = Math.pow(this.x, 2) + Math.pow(this.y, 2);
            this.d = Math.sqrt(r);
            
        }
    }
    
    static boolean cycle = false;
    
    static Stack<Integer> stack;
    static int[] dfs_low;
    static int[] dfs_num;
    static int timer;
    static int[] visit;
    
    static int[] string_match_basic(String S){
        
        int n = S.length();
        int[] L = new int[n];
        
        int index = 0;
        L[index] = 0; //base case
        
        while(index != n-1){
            
            int d = L[index];
            
            //System.out.println("at "+index+" is "+L[index]);
            
            while(S.charAt(d) != S.charAt(index+1) && d >0){
                d = L[d-1];
            }
            
            L[index+1] = S.charAt(d)==S.charAt(index+1) ? d+1 : 0;
            
            index+=1;
        }
        return L;
    }
    
    static class C{
        int w;
        int v;
        public C(int w, int v){
            this.w=w;
            this.v=v;
        }
    }
    
    
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new PrintWriter(System.out));
        
        
        String[] in = br.readLine().split(" ");
        
        int n = Integer.parseInt(in[0]);
        int m = Integer.parseInt(in[1]);
        
        String s = br.readLine();
        int[] p = new int[26];
        int[] a = new int[n];
        
        for(int i=0;i<26;i++){
            p[i]=i;
            
        }
        
        for(int i=0;i<s.length();i++){
            a[i] = (int)s.charAt(i) - 97;
            if(a[i]>25) System.exit(0);
        }
        
        for(int i=0;i<m;i++){
            in = br.readLine().split(" ");
            int x = (int)in[0].charAt(0)-97;
            int y = (int)in[1].charAt(0)-97;
            int tmp1 = 0;
            int tmp2 = 0;
            boolean seena =false;boolean seenb =false;
            for(int j=0;j<26;j++){
                if(p[j]==x){
                    //p[j] = y;
                    tmp1=j;
                    seena=true;
                    //System.out.println("changing "+j+" to "+y);
                    break;
                }
            }
            
            for(int k=0;k<26;k++){
                if(p[k]==y){
                   /// p[j] = x;
                    tmp2=k;
                    seenb=true;
                    //System.out.println("changing "+j+" to "+x);
                    break;
                }
            }
            
            if(tmp1>25||tmp2>25)    System.exit(0);
            p[tmp1]=y;
            p[tmp2]=x;
        }
        
        for(int i=0;i<n;i++){
            if(a[i]>25) System.exit(0);
            int t = p[a[i]];
            t+=97;
            bw.append((char)t+"");
        }
        bw.append("\n");
        bw.close();
    }
}