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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        KASimpleTask solver = new KASimpleTask();
        solver.solve(1, in, out);
        out.close();
    }

    static class KASimpleTask {
        int n;
        int q;
        char[] arr;

        public void readInput(Scanner sc) {
            n = sc.nextInt();
            q = sc.nextInt();
            arr = sc.next().toCharArray();
        }

        public void solve(int testNumber, Scanner sc, PrintWriter pw) {
            readInput(sc);
            int N = 1;
            while (N < n)
                N <<= 1;
            SegmentTree[] trees = new SegmentTree[26];
            for (int i = 0; i < 26; i++)
                trees[i] = new SegmentTree(N);
            for (int i = 0; i < n; i++) {
                trees[arr[i] - 'a'].update_range(i + 1, i + 1, 1);
            }
            for (int i = 0; i < q; i++) {
                int l = sc.nextInt(), r = sc.nextInt();
                int type = sc.nextInt();
                int s = type == 1 ? 0 : 25;
                int e = type == 1 ? 26 : -1;
                int add = type == 1 ? 1 : -1;
                int cur = l;
                for (int j = s; j != e; j += add) {
                    int sum = trees[j].query(l, r);
                    trees[j].update_range(l, r, 0);
                    trees[j].update_range(cur, cur + sum - 1, 1);
                    cur += sum;
                }
            }
            for (int i = 0; i < n; i++)
                for (int j = 0; j < 26; j++)
                    if (trees[j].query(i + 1, i + 1) == 1)
                        pw.print((char) ('a' + j));
        }

        public class SegmentTree {
            int N;
            int[] sTree;
            int[] lazy;

            SegmentTree(int N) {
                this.N = N;
                sTree = new int[N << 1];        //no. of nodes = 2*N - 1, we add one to cross out index zero
                lazy = new int[N << 1];
                Arrays.fill(lazy, -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) {
                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;

            }

        }

    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

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

    }
}