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

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner in = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        new Main().run(in, out);
        out.close();
    }

    int N, Q;
    void run(FastScanner in, PrintWriter out) {

        N = in.nextInt();
        Q = in.nextInt();

        getBounds(1, 0, N);

        char[] ca = in.next().toCharArray();
        for (int i = 0; i < N; i++) {
            updateRangeWithChar(1, ca[i]-'a', i, i);
        }

        while (Q-- > 0) {
            int l = in.nextInt()-1;
            int r = in.nextInt()-1;
            int k = in.nextInt();
            update(l, r, k);
        }

        for (int i = 0; i < N; i++) {
            for (int c = 0; c < 26; c++) {
                if (getCount(1, c, i, i) == 1) {
                    out.print((char)(c+'a'));
                    break;
                }
            }
        }
        out.println();

        // for (int i = 0; i < N; i++) {
        //     out.print(i + " ");
        //     for (int c = 0; c < 26; c++) {
        //         if (getCount(1, c, i, i) == 1) {
        //             out.print((char)(c+'a'));
        //             break;
        //         }
        //     }
        //     out.println();
        // }
        // out.println();
    }

    // build 26 segment trees. one for each character
    // when a query comes in, get the count for each character in that range
    // update the character trees
    int MAXN = 100_000;
    int[] lo = new int[4*MAXN+4];
    int[] hi = new int[4*MAXN+4];
    int[][] sum = new int[26][4*MAXN+4];
    int[][] delta = new int[26][4*MAXN+4];

    void getBounds(int i, int a, int b) {
        lo[i] = a;
        hi[i] = b;
        if (a == b) return;
        int m = (a+b)>>1;
        getBounds(2*i, a, m);
        getBounds(2*i+1, m+1, b);
    }

    int getCount(int i, int c, int a, int b) {
        if (b < lo[i] || a > hi[i]) return 0;
        if (a <= lo[i] && hi[i] <= b) {
            return sum[c][i];
        }

        prop(i, c);
        int ret = getCount(2*i, c, a, b) + getCount(2*i+1, c, a, b);
        sum[c][i] = sum[c][2*i] + sum[c][2*i+1];
        return ret;
    }

    void prop(int i, int c) {
        if (delta[c][i] == 0) return;
        if (2*i+1 >= sum[c].length) return;

        if (delta[c][i] == -1) {
            delta[c][2*i] = -1;
            sum[c][2*i] = 0;

            delta[c][2*i+1] = -1;
            sum[c][2*i+1] = 0;

            delta[c][i] = 0;
        } else {
            // need to keep clear-prop 1 step ahead
            if (delta[c][2*i] == -1) prop(2*i, c);

            delta[c][2*i] = delta[c][i];
            sum[c][2*i] += delta[c][i] * (hi[2*i]-lo[2*i]+1);

            if (delta[c][2*i+1] == -1) prop(2*i+1, c);
            delta[c][2*i+1] = delta[c][i];
            sum[c][2*i+1] += delta[c][i] * (hi[2*i+1]-lo[2*i+1]+1);
            delta[c][i] = 0;
        }
    }

    void clear(int i, int c, int a, int b) {
        if (b < lo[i] || a > hi[i]) return;
        if (a <= lo[i] && hi[i] <= b) {
            delta[c][i] = -1;
            sum[c][i] = 0;
            return;
        }

        prop(i, c);
        clear(2*i, c, a, b);
        clear(2*i+1, c, a, b);
        sum[c][i] = sum[c][2*i] + sum[c][2*i+1];
    }

    void updateRangeWithChar(int i, int c, int a, int b) {
        if (b < lo[i] || a > hi[i]) return;
        if (a <= lo[i] && hi[i] <= b) {
            if (delta[c][i] == -1) {
                if (lo[i] != hi[i]) prop(i ,c);
                delta[c][i] = 0;
            }

            delta[c][i] = 1;
            sum[c][i] += (hi[i]-lo[i]+1);
            return;
        }

        prop(i, c);
        updateRangeWithChar(2*i, c, a, b);
        updateRangeWithChar(2*i+1, c, a, b);
        sum[c][i] = sum[c][2*i] + sum[c][2*i+1];
    }


    int[] count = new int[26];
    void update(int a, int b, int k) {

        Arrays.fill(count, 0);

        // get number of each char
        for (int c = 0; c < 26; c++) {
            count[c] = getCount(1, c, a, b);
            clear(1, c, a, b);
        }

        int pos = a;
        if (k == 1) {
            for (int c = 0; c < 26; c++) {
                if (count[c] == 0) continue;
                updateRangeWithChar(1, c, pos, pos+count[c]-1);
                pos = pos+count[c];
            }
        } else {
            for (int c = 25; c >= 0; c--) {
                if (count[c] == 0) continue;
                updateRangeWithChar(1, c, pos, pos+count[c]-1);
                pos = pos+count[c];
            }
        }
    }






    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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