Problem: This task is very simple. Given a string S of length n and q queries each query is on the format i j k which means sort the substring consisting of the characters from i to j in non-decreasing order if k = 1 or in non-increasing order if k = 0.

Output the final string after applying the queries.

Input

The first line will contain two integers n, q (1 ≤ n ≤ 105, 0 ≤ q ≤ 50 000), the length of the string and the number of queries respectively. 

Next line contains a string S itself. It contains only lowercase English letters.

Next q lines will contain three integers each i, j, k (1 ≤ i ≤ j ≤ n, <image>).

Output

Output one line, the string S after applying the queries.

Examples

Input

10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1


Output

cbcaaaabdd

Input

10 1
agjucbvdfk
1 10 1


Output

abcdfgjkuv

Note

First sample test explanation:

<image>

<image>

<image>

<image>

<image>

Solution (in JAVA):

Solution:
/**
 * Created by Aminul on 8/12/2018.
 */

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class CF558E_2 {
    public static void main(String[] args)throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = in.nextInt(), q = in.nextInt();
        char[] s = in.next(n);
        SegTree [] segTree = new SegTree[26];
        for (int i = 0; i < 26; i++) {
            segTree[i] = new SegTree(n);
        }

        for (int i = 0; i < n; i++) {
            segTree[s[i]-'a'].update(i+1, i+1, 1);
        }

        for (int i = 0; i < q; i++) {
            int l = in.nextInt(), r = in.nextInt(), k = in.nextInt();
            if(k == 1){
                int idx = l;
                for(int p = 0; p < 26; p++){
                    int count = segTree[p].query(l, r);
                    segTree[p].update(l, r, 0);
                    segTree[p].update(idx, idx+count-1, 1);
                    idx += count;
                }
            }

            else{
                int idx = l;
                for(int p = 25; p >= 0; p--){
                    int count = segTree[p].query(l, r);
                    segTree[p].update(l, r, 0);
                    segTree[p].update(idx, idx+count-1, 1);
                    idx += count;
                }
            }
        }

        char[] res = new char[n];
        for (int p = 0; p < 26; p++) {
            for (int i = 1; i <= n; i++) {
                if(segTree[p].query(i, i) == 1) res[i-1] = (char) ('a' + p);
            }
        }

        pw.println(res);


        pw.close();
    }

    static class SegTree{
        int n, seg[], lazy[];
        boolean clear[];
        SegTree(int n){
            this.n = n;
            seg = new int[4*n];
            lazy = new int[4*n];
            clear = new boolean[4*n];
        }

        void pushDown(int p, int l, int r, int s, int m, int e){
            if(clear[p]) return;
            clear[l] = clear[r] = clear[p];
            lazy[l] = lazy[r] = lazy[p];
            seg[l] = (m-s+1)*lazy[l];
            seg[r] = (e-m) * lazy[r];
            clear[p] = true;
        }

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

        void update(int p, int s, int e, int a, int b, int v){
            if(s >= a && e <= b){
                clear[p] = false;
                lazy[p] = v;
                seg[p] = (e-s+1) * v;
                return;
            }
            if(s > e || s > b || e < a) return;
            int m = (s+e)/2, l = 2*p, r = l+1;
            pushDown(p, l, r, s, m, e);
            update(l, s, m, a, b, v);
            update(r, m+1, e, a, b, v);
            seg[p] = seg[l] + seg[r];
        }

        int query(int l, int r){
            return query(1, 1, n, l, r);
        }

        int query(int p, int s, int e, int a, int b){
            if(s >= a && e <= b) return seg[p];
            if(s > e || s > b || e < a) return 0;
            int m = (s+e)/2, l = 2*p, r = l+1;
            pushDown(p, l, r, s, m, e);
            return query(l, s, m, a, b) + query(r, m+1, e, a, b);
        }

    }

    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);
        }*/
    }
}