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.PrintWriter;
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;

import static java.lang.Math.*;

/* Built using CHelper plug-in
*/
public class codeforces{
    static class pair implements Comparable<pair> {
        int a, b;


        public pair(int a, int b) {
            this.a = a;
            this.b = b;
        }

        //@Override
        @Override
        public int compareTo(pair p) {
            return this.b - p.b;
        }
    }
    static  FastReader in;
    static PrintWriter out;
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        in = new FastReader(inputStream);
        out = new PrintWriter(outputStream);
        Ques solver;
        solver = new Ques();
        //int testNumber=in.nextInt();
        //while(testNumber-->0)
        solver.solve(1, in, out);
        out.flush();
        out.close();
    }
    static class Ques {
        int[] dr = new int[]{-1, 1, 0, 0};
        int[] dc = new int[]{0, 0, -1, 1};

        public void solve(int testNumber, FastReader in, PrintWriter out){
        int n=ni();
        int m=ni();
        String z=ns();
        char a[]=z.toCharArray();
        StringBuilder sb=new StringBuilder(z);
        int ans[]=new int[26];
        for(int i=0;i<26;i++) ans[i]=i+'a';
        while(m-->0) {
            char x=nc();
            char y=nc();
            for(int i=0;i<26;i++) {
                if(ans[i]==x){
                    ans[i]=y;
                }
                else if(ans[i]==y){
                    ans[i]=x;
                }
               // out.println(sb);
            }
           // out.println(sb);
        //   for(int i=0;i<sb.length();i++)
          //      a[i]=sb.charAt(i);
        }
        for(int i=0;i<n;i++) {
            out.print((char)ans[a[i]-'a']);
        }
        }
        private static int ni(){
            return in.nextInt();
        }
        private static long nl(){
            return in.nextLong();
        }
        private static String ns(){
            return in.nextString();
        }
        private static char nc(){
            return in.nextCharacter();
        }
        private static double nd(){
            return in.nextDouble();
        }

        private static char[] ns(int n) {
            char[] a = new char[n];
            for(int i=0;i<n;i++) a[i] = nc();
            return a;
        }

        private static char[][] nm(int n, int m)
        {
            char[][] map = new char[n][];
            for(int i=0;i<n;i++) map[i] = ns(m);
            return map;
        }

        private static int[] na(int n)
        {
            int[] a = new int[n];
            for(int i=0;i<n;i++) a[i] = ni();
            return a;
        }

        private static long[] nal(int n)
        {
            long[] a = new long[n];
            for(int i=0;i<n;i++) a[i] = nl();
            return a;
        }
    }

    static long lcm(long a, long b) { return (a * (b / GCD(a, b))); }
    static long  infinity=Long.MAX_VALUE;
    public static int[] radixSort(int[] f){ return radixSort(f, f.length); }
    public static int[] radixSort(int[] f, int n) {
        int[] to = new int[n];
        {
            int[] b = new int[65537];
            for(int i = 0;i < n;i++)b[1+(f[i]&0xffff)]++;
            for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
            for(int i = 0;i < n;i++)to[b[f[i]&0xffff]++] = f[i];
            int[] d = f; f = to;to = d;
        }
        {
            int[] b = new int[65537];
            for(int i = 0;i < n;i++)b[1+(f[i]>>>16)]++;
            for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
            for(int i = 0;i < n;i++)to[b[f[i]>>>16]++] = f[i];
            int[] d = f; f = to;to = d;
           }
        return f;
    }
    static final int MAXN = 1000001;
    // stores smallest prime factor for every number
    static int spf[] = new int[MAXN];
    // Calculating SPF (Smallest Prime Factor) for every
    // number till MAXN.
    // Time Complexity : O(nloglogn)
    static void sieve() {
        spf[1] = 1;
        for (int i=2; i<MAXN; i++)

            // marking smallest prime factor for every
            // number to be itself.
            spf[i] = i;

        // separately marking spf for every even
        // number as 2
        for (int i=4; i<MAXN; i+=2)
            spf[i] = 2;

        for (int i=3; i*i<MAXN; i++)
        {
            // checking if i is prime
            if (spf[i] == i)
            {
                // marking SPF for all numbers divisible by i
                for (int j=i*i; j<MAXN; j+=i)

                    // marking spf[j] if it is not
                    // previously marked
                    if (spf[j]==j)
                        spf[j] = i;
            }
        }
    }

    // A O(log n) function returning primefactorization
    // by dividing by smallest prime factor at every step
    static Vector<Integer> getFactorization(int x)
    {
        Vector<Integer> ret = new Vector<>();
        while (x != 1&&spf[x]!=0)
        {
            ret.add(spf[x]);
            x = x / spf[x];
        }
        return ret;
    }
    static long GCD(long a, long b) { return (a%b == 0)? Math.abs(b) : GCD(b,a%b); }
    static long ncr(long n,long r){
        if(r==0 || r==n) return 1;
        double d=1;
        if(r>n) r=n-r;
        for(int i=0;i<r;i++){
            d*=(double)(n-i)/(i+1);
        }
        return (long)d;
    }
    static long d, x, y;
    static void extendedEuclid(long A, long B) {
        if(B == 0) {
            d = A;
            x = 1;
            y = 0;
        }
        else {
            extendedEuclid(B, A%B);
            long temp = x;
            x = y;
            y = temp - (A/B)*y;
        }
    }
    static long modInverse(long A, long M)
    {
        extendedEuclid(A,M);
        return (x%M+M)%M;
    }
    static long modPow(long x,long y,long M){
        if(y==0) return 1;
        if(y%2==0) return modPow((x*x)%M,y/2,M);
        else return (x*modPow((x*x)%M,(y-1)/2,M))%M;
    }
    static long M = (long) Math.pow(10,9)+7;
    static long fact(long x){
        if(x==0 || x==1) return 1;
        return ((x%M) * (fact(x-1)%M))%M;
    }
    static long power(long x,long y){
        if(y==0) return 1;
        if(y%2==0) return power((x*x)%M,y/2)%M;
        else return (x*power((x*x)%M,(y-1)/2))%M;
    }
    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[8192];
        private int curChar;
        private int pnumChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (pnumChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= pnumChars) {
                curChar = 0;
                try {
                    pnumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (pnumChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }
        private String readLine0(){
            StringBuilder buf = new StringBuilder ();
            int c = read ();
            while (c != '\n' && c != -1){
                if (c != '\r'){
                    buf.appendCodePoint (c);
                }
                c = read ();
            }
            return buf.toString ();
        }
        public String nextLine(){
            String s = readLine0 ();
            while (s.trim ().length () == 0)
                s = readLine0 ();
            return s;
        }
        public String nextLine(boolean ignoreEmptyLines){
            if (ignoreEmptyLines){
                return nextLine ();
            }else{
                return readLine0 ();
            }
        }
        public char nextCharacter(){
            int c = read ();
            while (isSpaceChar (c))
                c = read ();
            return (char) c;
        }

        public double nextDouble(){
            int c = read ();
            while (isSpaceChar (c))
                c = read ();
            int sgn = 1;
            if (c == '-'){
                sgn = -1;
                c = read ();
            }
            double res = 0;
            while (!isSpaceChar (c) && c != '.'){
                if (c == 'e' || c == 'E'){
                    return res * Math.pow (10, nextInt ());
                }
                if (c < '0' || c > '9'){
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read ();
            }
            if (c == '.'){
                c = read ();
                double m = 1;
                while (!isSpaceChar (c)){
                    if (c == 'e' || c == 'E'){
                        return res * Math.pow (10, nextInt ());
                    }
                    if (c < '0' || c > '9'){
                        throw new InputMismatchException ();
                    }
                    m /= 10;
                    res += (c - '0') * m;
                    c = read ();
                }
            }
            return res * sgn;
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c == ',') {
                    c = read();
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
        public String next() {
            return nextString();
        }
        public int[] nextIntArray(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        public BigInteger nextBigInteger(){
            try{
                return new BigInteger (nextString());
            } catch (NumberFormatException e){
                throw new InputMismatchException ();
            }
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }


    }
}