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 static java.lang.Math.*;
import static java.util.Arrays.* ;

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

public class Main
{
    void main() throws Exception
    {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = sc.nextInt() ;
        int q = sc.nextInt() ;
        char [] s = sc.next().toCharArray() ;
        SegmentTree [] seg = new SegmentTree[26] ;
        for(int i = 0 ; i < 26 ; i++)
            seg[i] = new SegmentTree(n) ;
        for(int i = 0 ; i < n ; i ++)
            seg[s[i] - 'a'].update_point(i + 1 );

        while(q-->0)
        {
            int i = sc.nextInt() , j = sc.nextInt() , k = sc.nextInt() ;
            int start = i ;

            for(int c = k == 1 ? 0 : 25 ; k == 1 ? (c < 26) : (c >= 0);)
            {
                int end = start + seg[c].query(i , j) - 1;
                seg[c].update_range(i , j , 0);
                seg[c].update_range(start , end , 1);
                start = end + 1;
                if(k == 1) c++;
                else c -- ;
            }
        }
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < 26 ; j++)
                if (seg[j].query(i + 1, i + 1) ==  1)
                {
                    out.print((char) (j + 'a'));
                    break;
                }
        out.flush();
        out.close();
    }
    class SegmentTree
    {

        int N;
        int [] sTree, lazy;

        SegmentTree(int n)
        {
            N = 1 << (32 - Integer.numberOfLeadingZeros(n));
            sTree = new int[N << 1];
            lazy = new int[N << 1];
            fill(lazy , -1);
        }

        void update_point(int index)
        {
            index += N - 1;
            sTree[index] ++;
            while (index > 1)
            {
                index >>= 1;
                sTree[index] = sTree[index << 1] + sTree[index << 1 | 1];
            }
        }


        void update_range(int i, int j, int val)
        {
            update_range(1, 1, N, i, j, val);
        }

        void update_range(int node, int b, int e, int i, int j, int val)
        {
            if (i > e || j < b)
                return;
            if (b >= i && e <= j) {
                sTree[node] = (e - b + 1) * val;
                lazy[node] = val;
            } else {
                int mid = b + e >> 1;
                propagate(node, b, mid, e);
                update_range(node << 1, b, mid, i, j, val);
                update_range(node << 1 | 1, mid + 1, e, i, j, val);
                sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
            }
        }
        void propagate(int node, int b, int mid, int e)
        {
            if(lazy[node] == -1)return;
            lazy[node << 1] = lazy[node];
            lazy[node << 1 | 1] = lazy[node];
            sTree[node << 1] = (mid - b + 1) * lazy[node];
            sTree[node << 1 | 1] = (e - mid) * lazy[node];
            lazy[node] = -1;
        }

        int query(int i, int j) {
            return query(1, 1, N, i, j);
        }

        int query(int node, int b, int e, int i, int j)    // O(log n)
        {
            if (i > e || j < b)
                return 0;
            if (b >= i && e <= j)
                return sTree[node];
            int mid = b + e >> 1;
            propagate(node, b, mid, e);
            int q1 = query(node << 1, b, mid, i, j);
            int q2 = query(node << 1 | 1, mid + 1, e, i, j);
            return q1 + q2;

        }
    }

    class Scanner
    {
        BufferedReader br;
        StringTokenizer st;

        Scanner(InputStream in)
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws Exception
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

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

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

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

    public static void main (String [] args) throws Exception {(new Main()).main();}

}