Petya has a string of length n consisting of small and large English letters and digits.

He performs m operations. Each operation is described with two integers l and r and a character c: Petya removes from the string all characters c on positions between l and r, inclusive. It's obvious that the length of the string remains the same or decreases after each operation.

Find how the string will look like after Petya performs all m operations.

Input

The first string contains two integers n and m (1 ≤ n, m ≤ 2·105) — the length of the string and the number of operations.

The second line contains the string of length n, consisting of small and large English letters and digits. Positions in the string are enumerated from 1.

Each of the next m lines contains two integers l and r (1 ≤ l ≤ r), followed by a character c, which is a small or large English letter or a digit. This line describes one operation. It is guaranteed that r doesn't exceed the length of the string s before current operation.

Output

Print the string Petya will obtain after performing all m operations. If the strings becomes empty after all operations, print an empty line.

Examples

Input

4 2
abac
1 3 a
2 2 c


Output

b


Input

3 2
A0z
1 3 0
1 1 z


Output

Az


Input

10 4
agtFrgF4aF
2 5 g
4 9 F
1 5 4
1 7 a


Output

tFrg4


Input

9 5
aAAaBBccD
1 4 a
5 6 c
2 3 B
4 4 D
2 3 A


Output

AB

Note

In the first example during the first operation both letters 'a' are removed, so the string becomes "bc". During the second operation the letter 'c' (on the second position) is removed, and the string becomes "b".

In the second example during the first operation Petya removes '0' from the second position. After that the string becomes "Az". During the second operations the string doesn't change.
/**
 * Created by Aminul on 12/17/2017.
 */

import java.io.*;
import java.util.*;

public class F_2 {
    static char str[];
    static long arr[];
    public static void main(String[] args) throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        build();
        int n = in.nextInt(), q = in.nextInt();
        str = in.next(n);

        SegTree segTree = new SegTree(n);
        segTree.build();
        for(int i = 0 ; i < q; i++){
            int l = in.nextInt(), r = in.nextInt(), v = charToint[in.nextChar()];
            l = segTree.getId(l); r = segTree.getId(r); //debug(l, r, v);
            segTree.update(l, r, v);
        }

        arr = new long[n];
        segTree.build_array();

        for(int i = 0; i < n; i++){
            if(arr[i] != 0) pw.print(str[i]);
        }
        pw.println();



        pw.close();
    }

    static int charToint[] = new int[200];
    static char intTochar[] = new char[200];
    static void build(){
        int i = -1;
        for(char k = 'A'; k <= 'Z'; k++){
            charToint[k] = ++i;
            intTochar[i] = k;
        }
        for(char k = 'a'; k <= 'z'; k++){
            charToint[k] = ++i;
            intTochar[i] = k;
        }
        for(char k = '0'; k <= '9'; k++){
            charToint[k] = ++i;
            intTochar[i] = k;
        }
    }

    static boolean check(long N, int pos){return (N & (1l<<pos)) != 0;}
    static long set(long N, int pos){return N=N | (1l<<pos);}
    static long reset(long N, int pos){return N= N & ~(1l<<pos);}


    static class SegTree{
        int n, sum[];
        long  bits[];
        SegTree(int N){
            n =  N;
            sum = new int[4*n];
            bits = new long[4*n];
        }

        void update(int l, int r, int v){
            update(1, 1, n, l, r, v);
        }

        int getId(int i){
            return getId(1, 1, n, i);
        }

        void build(){
            build(1, 1, n);
        }


        void build(int p, int s, int e){
            if(s == e){
                sum[p]++;
                bits[p] = set(0, charToint[str[s-1]]);
                return;
            }
            int m = (s+e)/2, l = 2*p, r = l+1;
            build(l,s, m);
            build(r, m+1, e);
            sum[p] = sum[l] + sum[r];
            bits[p] =  bits[l] | bits[r];
        }


        int getId(int p, int s, int e, int i){
            if(s == e) return s;
            if(s > e) return -1;
            int m = (s+e)/2, l = 2*p, r = l+1;
            if(sum[l] >= i) return getId(l, s, m, i);
            return getId(r, m+1, e, i - sum[l]);
        }


        void update(int p, int s, int e, int a, int b, int v){
            if(s > e || s > b || e < a) return;
            if(s == e && s >= a && e <= b){
                if(check(bits[p], v))bits[p] = sum[p] = 0;
                return;
            }
            int m = (s+e)/2, l = 2*p, r = l+1;
            if(check(bits[l], v)) update(l, s, m, a, b, v);
            if(check(bits[r], v)) update(r, m+1, e, a, b, v);
            sum[p] = sum[l] + sum[r];
            bits[p] =  bits[l] | bits[r];
        }

        void build_array(){
            build_array(1, 1, n);
        }

        void build_array(int p, int s, int e){
            if(s == e){
                arr[s-1] = bits[p];
                return;
            }
            int m = (s+e)/2, l = 2*p, r = l+1;
            build_array(l,s, m);
            build_array(r, m+1, e);
        }
    }


    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;
        static final int ints[] = new int[128];

        public FastReader(InputStream is) {
            for (int i = '0'; i <= '9'; i++) ints[i] = i - '0';
            this.is = is;
        }

        public int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }

        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;
            return b;
        }

        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + ints[b];
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + ints[b];
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
        public char nextChar() {
            return (char)skip();
        }

        public char[] next(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        /*private char buff[] = new char[1005];
        public char[] nextCharArray(){
            int b = skip(), p = 0;
            while(!(isSpaceChar(b))){
                buff[p++] = (char)b;
                b = readByte();
            }
            return Arrays.copyOf(buff, p);
        }*/
    }
}