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:
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Contest558E {
    public static PrintWriter out = new PrintWriter(System.out);
    public static FastScanner enter = new FastScanner(System.in);
    public static String s;
    public static void main(String[] args) throws IOException {
        solve();
        out.close();
    }

    private static void solve() throws IOException{
        int n=enter.nextInt();
        int m=enter.nextInt();
        s=enter.next();
        SegmentTree[] tree = new SegmentTree[26];
        for (int i = 0; i <26 ; i++) {
          tree[i]=new SegmentTree((char)(i+'a'));
          tree[i].build(1,0, s.length()-1);
        }
        int[] counter=new int[26];
        for (int i = 0; i <m ; i++) {
            int l=enter.nextInt();
            int r=enter.nextInt();
            int k=enter.nextInt();
            for (int j = 0; j <26 ; j++) {
                counter[j]=tree[j].query(1, 0, s.length()-1, l-1, r-1);
            }
            if(k==1){
                int summ=0;
                for (int j = 0; j <26 ; j++) {
                    tree[j].update(1,0,s.length()-1,l-1,l+summ-2, 0);
                    tree[j].update(1,0,s.length()-1,l+summ-1, l+summ-2+counter[j], 1);
                    tree[j].update(1,0,s.length()-1,l+summ-1+counter[j],r-1,0);
                    summ+=counter[j];
                }
            }
            else{
                int summ=0;
                for (int j = 0; j <26 ; j++) {
                    tree[25-j].update(1,0,s.length()-1,l-1,l+summ-2, 0);
                    tree[25-j].update(1,0,s.length()-1,l+summ-1, l+summ-2+counter[25-j], 1);
                    tree[25-j].update(1,0,s.length()-1,l+summ-1+counter[25-j],r-1,0);
                    summ+=counter[25-j];
                }
            }
        }

        for (int i = 0; i <s.length() ; i++) {
            char a='$';
            for (int j = 0; j <26 ; j++) {
                int v=tree[j].query(1,0,s.length()-1,i,i);
                if(v!=0) a=(char)('a'+j);
            }
            out.print(a);
        }



    }

    static class SegmentTree{
        char type;
        int[] t;
        int[] lazy;

        public SegmentTree(char type) {
            this.type = type;
            t=new int[s.length()*4+1];
            lazy=new int[s.length()*4+1];
            Arrays.fill(lazy,-1);
        }
        public void update(int v, int vl, int vr, int l,int r, int p){
            if(l>r) return;
            if(l==vl && vr==r){
                lazy[v]=p;
                if(vl==vr) lazy[v]=-1;
                else push(v);
                t[v]=p*(r-l+1);
                return;
            }
            int tmp = (vl+vr)/2;
            push(v);
            update(2*v, vl, tmp, l, Math.min(r, tmp), p);
            update(2*v+1, tmp+1, vr, Math.max(tmp+1,l), r, p);
            t[v]=get(2*v, vl, tmp)+get(2*v+1, tmp+1, vr);
        }
        public int get(int v, int l, int r){
            return (lazy[v]==-1) ? t[v] : (lazy[v]*(r-l+1));
        }

        public int query(int v, int vl, int vr, int l, int r){
            if(l>r) return 0;
            if(l==vl && r==vr){
                return get(v,vl,vr);
            }
            int tmp = (vl+vr)/2;
            if(lazy[v]!=-1) return lazy[v]*(r-l+1);
            return query(2*v, vl, tmp,l, Math.min(r, tmp))+query(2*v+1, tmp+1, vr, Math.max(l, tmp+1), r);
        }

        public void push(int v){
            if(lazy[v]!=-1) {
                lazy[2 * v] = lazy[v];
                lazy[2 * v + 1] = lazy[v];
                lazy[v] = -1;
            }
        }
        public void build(int v, int vl, int vr){
            if(vl==vr) {
                t[v] = (s.charAt(vl)==type) ? 1:0;
                return;
            }
            int tmp=(vl+vr)/2;
            build(2*v, vl, tmp);
            build(2*v+1, tmp+1, vr);
            t[v]=t[2*v]+t[2*v+1];
        }

    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer stok;

        FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        String next() throws IOException {
            while (stok == null || !stok.hasMoreTokens()) {
                String s = br.readLine();
                if (s == null) {
                    return null;
                }
                stok = new StringTokenizer(s);
            }
            return stok.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        char nextChar() throws IOException {
            return (char) (br.read());
        }

        String nextLine() throws IOException {
            return br.readLine();
        }
    }
}