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.
import java.util.*;
import java.io.*;
import java.math.*;

public class f {

    static int n, m;
    static SuperBIT bit;
    
    public static void main(String[] args) throws IOException {
        FastScanner in = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        
        n = in.nextInt();
        m = in.nextInt();
        
        bit = new SuperBIT(n + 2);
        char[] str = in.next().toCharArray();
        
        int[] nexts = new int[n];
        int[] prevs = new int[n];
        int[] idxs = new int[256];
        boolean[] valid = new boolean[n];
        Arrays.fill(valid, true);
        PersistentTreap<Integer, Integer>[] treaps = new PersistentTreap[256];
        for (int i = 0; i < 256; i++)
            treaps[i] = new PersistentTreap<>();
        Arrays.fill(nexts, -1);
        Arrays.fill(idxs, -1);
        for (int i = 0; i < n; i++) {
            int c = (int) str[i];
            treaps[c] = treaps[c].add(i);
            prevs[i] = idxs[c];
            if (idxs[c] != -1)
                nexts[idxs[c]] = i;
            idxs[c] = i;
        }
        
        for (int i = 0; i < m; i++) {
            int left = in.nextInt() - 1;
            int right = in.nextInt() - 1;
            int c = (int) in.next().charAt(0);
            int v = findFirst(treaps[c], left, right);
            int off = 0;
            while (v != -1) {
                int idx = getIndex(v) + off++;
                if (idx > right) break;
                valid[v] = false;
                treaps[c] = treaps[c].remove(v);
                bit.update(v + 1, n + 1, -1);
                
                if (prevs[v] != -1)
                    nexts[prevs[v]] = nexts[v];
                if (nexts[v] != -1)
                    prevs[nexts[v]] = prevs[v];
                
                v = nexts[v];
            }
        }
        
        for (int i = 0; i < n; i++)
            if (valid[i])
                out.print(str[i]);
        out.println();
        
        out.close();
    }

    static int findFirst(PersistentTreap<Integer, Integer> t, int left, int right) {
        if (t.size() == 0) return -1;
        return bs(t, 0, t.size() - 1, left, right);
    }
    
    static int bs(PersistentTreap<Integer, Integer> t, int min, int max, int left, int right) {
        if (min + 1 >= max) {
            int tmp = t.get(min).key;
            int idx = getIndex(tmp);
            if (idx >= left && idx <= right)
                return tmp;
            tmp = t.get(max).key;
            idx = getIndex(tmp);
            if (idx >= left && idx <= right)
                return tmp;
            return -1;
        }
        int mid = (min + max) / 2;
        int idx = getIndex(t.get(mid).key);
        if (idx < left)
            return bs(t, mid, max, left, right);
        return bs(t, min, mid, left, right);
    }
    
    static int getIndex(int i) {
        return i + (int) bit.query(i + 1, i + 1);
    }
    static class PersistentTreap<K, V> {
        private final Comparator<? super K> comparator;
        Node<K,V> root;
        Random random;
        long king;
        
        public PersistentTreap() {
            comparator = null;
            random = new Random();
            king = -1;
        }
        public PersistentTreap(Comparator<? super K> comparator) {
            this.comparator = comparator;
            random = new Random();
            king = -1;
        }
        public PersistentTreap(PersistentTreap<K,V> treap) {
            comparator = treap.comparator;
            random = treap.random;
            king = treap.king;
            root = treap.root;
            if (root != null)
                root = new Node<K,V>(root);
        }
        public PersistentTreap<K,V> add(K key) {
            return put(key, null);
        }
        public PersistentTreap<K,V> put(K key, V val) {
            PersistentTreap<K,V> treap = new PersistentTreap<K,V>(this);
            treap.root = add(treap.root, key, val);
            return treap;
        }
        private Node<K,V> add(Node<K,V> cur, K key, V val) {
            if (cur == null)
                return new Node<K,V>(key, val, random.nextLong() & 0x7FFFFFFFFFFFFFFFL);
            int comp = compareKeys(key, cur.key);
            if (comp == 0) return cur;
            if (comp < 0) {
                cur.cloneLeftChild();
                cur.left = add(cur.left, key, val);
                return rotateLeft(cur);
            } else {
                cur.cloneRightChild();
                cur.right = add(cur.right, key, val);
                return rotateRight(cur);
            }
        }
        private Node<K,V> rotateLeft(Node<K,V> cur) {
            if (cur.left == null || cur.left.p > cur.p) {
                cur.update();
                return cur;
            }
            Node<K,V> c = cur.left;
            c.cloneRightChild();
            cur.left = c.right;
            c.right = cur;
            cur.update();
            c.update();
            return c;
        }
        private Node<K,V> rotateRight(Node<K,V> cur) {
            if (cur.right == null || cur.right.p > cur.p) {
                cur.update();
                return cur;
            }
            Node<K,V> c = cur.right;
            c.cloneRightChild();
            cur.right = c.left;
            c.left = cur;
            cur.update();
            c.update();
            return c;
        }
        public PersistentTreap<K,V> remove(K key) {
            Node<K,V> node = find(key);
            if (node == null) return this;
            PersistentTreap<K,V> treap = makeRoot(key);
            treap.root.update();
            treap.root.cloneChildren();
            treap.root = meld(treap.root.left, treap.root.right);
            return treap;
        }
        private Node<K,V> meld(Node<K,V> left, Node<K,V> right) {
            if (left == null || right == null)
                return left == null ? right : left;
            if (left.p <= right.p) {
                left.cloneRightChild();
                left.right = meld(left.right, right);
                left.update();
                return left;
            } else {
                right.cloneLeftChild();
                right.left = meld(left, right.left);
                right.update();
                return right;
            }
        }
        public PersistentTreap<K,V> makeRoot(K key) {
            PersistentTreap<K,V> treap = new PersistentTreap<K,V>(this);
            treap.root = makeRoot(treap.root, key);
            return treap;
        }
        private Node<K,V> makeRoot(Node<K,V> cur, K key) {
            if (cur == null)
                return cur;
            int comp = compareKeys(key, cur.key);
            if (comp < 0) {
                cur.cloneLeftChild();
                cur.left = makeRoot(cur.left, key);
                cur.update();
                return rotateLeft(cur);
            } else if (comp > 0) {
                cur.cloneRightChild();
                cur.right = makeRoot(cur.right, key);
                cur.update();
                return rotateRight(cur);
            }
            cur.p = king--;
            cur.update();
            return cur;
        }
        public Node<K,V> find(K key) {
            Node<K,V> cur = root;
            while (cur != null) {
                cur.update();
                int comp = compareKeys(key, cur.key);
                if (comp == 0) break;
                cur = comp < 0 ? cur.left : cur.right;
            }
            return cur;
        }
        boolean contains(K key) {
            return containsKey(key);
        }
        boolean containsKey(K key) {
            return find(key) != null;
        }
        public K ceiling(K key) {
            return ceilingKey(key);
        }
        public K ceilingKey(K key) {
            Node<K,V> tmp = ceilingNode(key);
            return tmp == null ? null : tmp.key;
        }
        public K higher(K key) {
            return higherKey(key);
        }
        public K higherKey(K key) {
            Node<K,V> tmp = higherNode(key);
            return tmp == null ? null : tmp.key;
        }
        public K floor(K key) {
            return floorKey(key);
        }
        public K floorKey(K key) {
            Node<K,V> tmp = floorNode(key);
            return tmp == null ? null : tmp.key;
        }
        public K lower(K key) {
            return lowerKey(key);
        }
        public K lowerKey(K key) {
            Node<K,V> tmp = lowerNode(key);
            return tmp == null ? null : tmp.key;
        }
        public K first(K key) {
            return firstKey(key);
        }
        public K firstKey(K key) {
            Node<K,V> tmp = firstNode();
            return tmp == null ? null : tmp.key;
        }
        public K last(K key) {
            return lastKey(key);
        }
        public K lastKey(K key) {
            Node<K,V> tmp = lastNode();
            return tmp == null ? null : tmp.key;
        }
        public Node<K,V> ceilingNode(K key) {
            return ceilingNode(root, key);
        }
        private Node<K,V> ceilingNode(Node<K,V> cur, K key) {
            if (cur == null)
                return cur;
            int comp = compareKeys(key, cur.key);
            if (comp < 0) {
                Node<K, V> better = ceilingNode(cur.left, key);
                if (better != null) return better;
            } else if (comp > 0) {
                return ceilingNode(cur.right, key);
            }
            return cur;
        }
        public Node<K,V> higherNode(K key) {
            return higherNode(root, key);
        }
        private Node<K,V> higherNode(Node<K,V> cur, K key) {
            if (cur == null)
                return cur;
            int comp = compareKeys(key, cur.key);
            if (comp < 0) {
                Node<K, V> better = higherNode(cur.left, key);
                if (better != null) return better;
            } else if (comp >= 0) {
                return higherNode(cur.right, key);
            }
            return cur;
        }
        public Node<K,V> floorNode(K key) {
            return floorNode(root, key);
        }
        private Node<K,V> floorNode(Node<K,V> cur, K key) {
            if (cur == null)
                return cur;
            int comp = compareKeys(key, cur.key);
            if (comp < 0) {
                return floorNode(cur.left, key);
            } else if (comp > 0) {
                Node<K,V> better = floorNode(cur.right, key);
                if (better != null) return better;
            }
            return cur;
        }
        public Node<K,V> lowerNode(K key) {
            return lowerNode(root, key);
        }
        private Node<K,V> lowerNode(Node<K,V> cur, K key) {
            if (cur == null)
                return cur;
            int comp = compareKeys(key, cur.key);
            if (comp <= 0) {
                return lowerNode(cur.left, key);
            } else if (comp > 0) {
                Node<K,V> better = lowerNode(cur.right, key);
                if (better != null) return better;
            }
            return cur;
        }
        public Node<K,V> get(int idx) {
            Node<K,V> cur = root;
            while (cur != null) {
                cur.update();
                int left = getSize(cur.left);
                if (left == idx) break;
                if (idx < left) {
                    cur = cur.left;
                } else {
                    cur = cur.right;
                    idx -= left + 1;
                }
            }
            return cur;
        }
        public Node<K,V> firstNode() {
            Node<K,V> cur = root;
            while (cur != null && cur.left != null)
                cur = cur.left;
            return cur;
        }
        public Node<K,V> lastNode() {
            Node<K,V> cur = root;
            while (cur != null && cur.right != null)
                cur = cur.right;
            return cur;
        }
        public int getSize(Node<K, V> node) {
            return node == null ? 0 : node.size;
        }
        public int size() {
            return getSize(root);
        }
        @SuppressWarnings("unchecked")
        private int compareKeys(K a, K b) {
            if (comparator != null)
                return comparator.compare(a, b);
            return ((Comparable<? super K>) a).compareTo(b);
        }
        
        @SuppressWarnings("unchecked")
        class Node<K, V> {
            private Node<K,V> left = null, right = null;
            public K key;
            public V val;
            private long p;
            private int size;
            
            public Node(K key, V val) {
                this.key = key;
                this.val = val;
                update();
                resetPriority();
            }
            public Node(K key, V val, long p) {
                this.key = key;
                this.val = val;
                this.p = p;
                update();
            }
            public Node(Node<K,V> node) {
                key = node.key;
                val = node.val;
                left = node.left;
                right = node.right;
                size = node.size;
                p = node.p;
            }
            private void cloneChildren() {
                cloneLeftChild();
                cloneRightChild();
            }
            private void cloneLeftChild() {
                if (left != null)
                    left = new Node<K,V>(left);
            }
            private void cloneRightChild() {
                if (right != null)
                    right = new Node<K,V>(right);
            }
            private void resetPriority() {
                p = PersistentTreap.this.random.nextLong() & 0x7FFFFFFFFFFFFFFFL;
            }
            private void update() {
                size = 1;
                if (left != null) size += left.size;
                if (right != null) size += right.size;
            }
        }
    }
static class SuperBIT {
  long[] dataMul, dataAdd;
  SuperBIT(int n) {
    dataMul = new long[n];
    dataAdd = new long[n];
  }
  void update(int left, int right, long val) {
    internalUpdate(left, val, -val * (left-1));
    internalUpdate(right, -val, val * right);
  }
  void internalUpdate(int at, long mul, long add) {
    while (at < dataMul.length) {
      dataMul[at] += mul;
      dataAdd[at] += add;
      at |= (at + 1);
    }
  }
  long query(int at) {
    long mul = 0;
    long add = 0;
    int start = at;
    while(at >= 0) {
      mul += dataMul[at];
      add += dataAdd[at];
      at = (at & (at + 1)) -1;
    }
    return mul * start + add;
  }
  long query(int left, int right) {
    if (left > right) {
      int temp = left;
      left = right;
      right = temp;
    }
    return query(right) - (left > 0 ? query(left-1) : 0);
  }
  long[] indices; // Used for compressed BIT
  // Compressed BIT constructor
  // A BIT that only stores the values that will be updated. 
  // indices is a sorted array of all the unique indices 
  // that would be used for this BIT.
  public SuperBIT(long[] indices) {
    this.indices = indices;
    dataMul = new long[indices.length];
    dataAdd = new long[indices.length];
  }
 
  // Search for the index in the array. If the index was not found, 
  // return the first index lower than the search index.
  int binSearch(int ind) {
    int low = 0;
    int high = dataMul.length-1;
    while(low < high) {
      int mid = (low + high+1)/2;
      if(indices[mid] == ind)
        return mid;
      else if(indices[mid] < ind) 
        low = mid;
      else if(indices[mid] > ind) 
        high = mid-1;
    }
    if(indices[low] > ind)
      --low;
    return low;
  }
  
  // Read the largest index less than or equal to the given index.
  long queryCompr(int index) {
    return query(binSearch(index));
  }
  long queryCompr(int left, int right) {
    return query(binSearch(left), binSearch(right));
  }
  // Update a specific index by a value. If the index is not in this 
  // compressed BIT, the index below will be updated.
  void updateCompr(int index, long val) {
    int ind = binSearch(index);
    update(ind, ind, val);
  }
  void updateCompr(int left, int right, long val) {
    update(binSearch(left), binSearch(right), val);
  } 
}
    static Random rand = new Random();
    static void sort(int[] a) {
        int n = a.length;
        for (int i = a.length - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
        Arrays.sort(a);
    }
    static void sort(long[] a) {
        int n = a.length;
        for (int i = a.length - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            long tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
        Arrays.sort(a);
    }
    static void sort(double[] a) {
        int n = a.length;
        for (int i = a.length - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            double tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
        Arrays.sort(a);
    }
    static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
    static long lcm(long a, long b) { return a / gcd(a, b) * b; }
    static long[] eEuclid(long a, long b) {
        if (b == 0) return new long[] { a, 1, 0 };
        long[] ans = eEuclid(b, a % b);
        long temp = ans[1] - ans[2] * (a / b);
        ans[1] = ans[2];  ans[2] = temp;
        return ans;
    }
    static long modInverse(long a, long m) {
        return ((eEuclid(a, m)[1] % m) + m) % m;
    }
    static class IntList {
        static int[] EMPTY = {};
        int[] a = EMPTY;
        int n = 0;
        void add(int v) {
            if (n >= a.length)
                a = Arrays.copyOf(a, (n << 2) + 8);
            a[n++] = v;
        }
        int get(int idx) {
            return a[idx];
        }
        int size() {
            return n;
        }
    }
    static class DisjointSet {
        int[] s, r;	
	public DisjointSet(int n) {
            s = new int[n]; r = new int[n];
            for (int i = 0; i < n; i++) s[i] = i;
        }	
        public int find(int i) { return s[i] == i ? i : (s[i] = find(s[i])); }
	public void union(int a, int b) {
            if(r[a = find(a)] == r[b = find(b)]) r[a]++;
            if(r[a] >= r[b]) s[b] = a; else s[a] = b;
        }
    }
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        public FastScanner(InputStream i) {
            br = new BufferedReader(new InputStreamReader(i));
            st = new StringTokenizer("");
        }
        public String next() throws IOException {
            if(st.hasMoreTokens())
                return st.nextToken();
            else
                st = new StringTokenizer(br.readLine());
            return next();
        }
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
        public int[] nextOffsetIntArray(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextInt() - 1;
            return arr;
        }
        public int[] nextIntArray(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextInt();
            return arr;
        }
        public int[][] nextIntArray(int n, int m) throws IOException {
            int[][] arr = new int[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    arr[i][j] = nextInt();
            return arr;
        }
        public long[] nextLongArray(int n) throws IOException {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextLong();
            return arr;
        }
        public long[][] nextLongArray(int n, int m) throws IOException {
            long[][] arr = new long[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    arr[i][j] = nextLong();
            return arr;
        }
        public double[] nextDoubleArray(int n) throws IOException {
            double[] arr = new double[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextDouble();
            return arr;
        }
        public double[][] nextDoubleArray(int n, int m) throws IOException {
            double[][] arr = new double[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    arr[i][j] = nextDouble();
            return arr;
        }
        public char[][] nextCharArray(int n, int m) throws IOException {
            char[][] arr = new char[n][];
            for (int i = 0; i < n; i++)
                arr[i] = next().toCharArray();
            return arr;
        }
    }
}
