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.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;


public class E {

    static StringTokenizer st;
    static BufferedReader br;
    static PrintWriter pw;
    static int[]t_color;
    static int [][]sum;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        int n = nextInt();
        int q = nextInt();
        int[]a = new int[n+1];
        String s = next();
        for (int i = 1; i <= n; i++) {
            a[i] = s.charAt(i-1) - 'a';
        }
        sum = new int[26][4*n];
        t_color = new int[4*n];
        Build(1, 1, n, a);
        Arrays.fill(t_color, -1);
        while (q-->0) {
            int L = nextInt();
            int R = nextInt();
            int tip = nextInt();
            int[]b = get(1, 1, n, L, R);
            if (tip==1) {
                int left = L;
                for (int i = 0; i < 26; i++) {
                    update(1, 1, n, left, left+b[i]-1, i);
                    left += b[i];
                }
            }
            else {
                int right = R;
                for (int i = 0; i < 26; i++) {
                    update(1, 1, n, right-b[i]+1, right, i);
                    right -= b[i];
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            int[]b = get(1, 1, n, i, i);
            for (int j = 0; j < 26; j++) {
                if (b[j] != 0) {
                    pw.print((char)(j+'a'));
                }
            }
        }
        pw.close();
    }
    private static void update(int v, int tl, int tr, int L, int R, int x) {
        if (L > R)
            return;
        if (tl==L && tr==R) {
            t_color[v] = x;
            for (int i = 0; i < 26; i++) {
                sum[i][v] = 0;
            }
            sum[x][v] = R-L+1;
            return;
        }
        int tm = (tl+tr) >> 1;
        if (t_color[v] != -1)
            push(v, tl, tm, tr);
        update(2*v, tl, tm, L, Math.min(tm, R), x);
        update(2*v+1, tm+1, tr, Math.max(L, tm+1), R, x);
        for (int i = 0; i < 26; i++) {
            sum[i][v] = sum[i][2*v] + sum[i][2*v+1];
        }
    }
    private static int[] get(int v, int tl, int tr, int L, int R) {
        if (L > R) {
            int[]a = new int[26];
            return a;
        }
        if (tl==L && tr==R) {
            int[]a = new int[26];
            if (t_color[v] != -1) {
                a[t_color[v]] = R-L+1;
            }
            else {
                for (int i = 0; i < 26; i++) {
                    a[i] = sum[i][v];
                }
            }
            return a;
        }
        int tm = (tl+tr) >> 1;
        if (t_color[v] != -1)
            push(v, tl, tm, tr);    
        int[]b = get(2*v, tl, tm, L, Math.min(tm, R));
        int[]c = get(2*v+1, tm+1, tr, Math.max(L, tm+1), R);
        int[]a = new int[26];
        for (int i = 0; i < 26; i++) {
            a[i] = b[i] + c[i];
        }
        for (int i = 0; i < 26; i++) {
            sum[i][v] = sum[i][2*v] + sum[i][2*v+1];
        }
        return a;
    }
    private static void push(int v, int tl, int tm, int tr) {
        t_color[2*v] = t_color[2*v+1] = t_color[v];
        for (int i = 0; i < 26; i++) {
            sum[i][2*v] = 0;
            sum[i][2*v+1] = 0;
        }
        sum[t_color[v]][2*v] = tm-tl+1;
        sum[t_color[v]][2*v+1] = tr-tm;
        t_color[v] = -1;
    }
    private static void Build(int v, int tl, int tr, int[] a) {
        if (tl==tr) {
            t_color[v] = a[tl];
            sum[a[tl]][v] = 1;
        }
        else {
            int tm = (tl+tr) >> 1;
            Build(2*v, tl, tm, a);
            Build(2*v+1, tm+1, tr, a);
            for (int i = 0; i < 26; i++) {
                sum[i][v] = sum[i][2*v] + sum[i][2*v+1];
            }
        }
    }
    private static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    private static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
    private static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
    private static String next() throws IOException {
        while (st==null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
}