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 Main {

    public static void main(String[] args) throws IOException {
        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();
        int N = 1;
        while (N < n)
            N <<= 1;
        SegmentTree st[] = new SegmentTree[26];
        for (int i = 0; i < 26; i++)
            st[i] = new SegmentTree(N);
        for (int i = 1; i <= n; i++) {
            char current = s[i - 1];
            st[current - 'a'].update_point(i, 1);
        }
        while (q-- > 0) {
            int left = sc.nextInt();
            int right = sc.nextInt();
            int k = sc.nextInt();
            int[] cnt = new int[26];
            for (int i = 0; i < 26; i++) {
                cnt[i] = st[i].query(left, right);
                st[i].update_range(left, right, 0);
            }
            if (k == 1) {
                for (int i = 0; i < 26; i++) {
                    int rt = cnt[i] + left - 1;
                    st[i].update_range(left, rt, 1);
                    left = rt + 1;
                }

            } else {
                for (int i = 25; i >= 0; i--) {
                    int rt = cnt[i] + left - 1;
                    st[i].update_range(left, rt, 1);
                    left = rt + 1;
                }
            }
//            System.err.println(getString(st, n));
        }
        out.println(getString(st, n));
        out.flush();
        out.close();
    }

    static String getString(SegmentTree[] st, int n) {
        StringBuilder ans = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 26; j++)
                if (st[j].query(i, i) == 1) {
                    ans.append((char) (j + 'a'));
                    break;
                }
        }
        return ans.toString();
    }

    static class Scanner {
        BufferedReader br;
        StringTokenizer st;

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

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

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

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

    static class SegmentTree {

        int N;
        int[] sTree, lazy;

        SegmentTree(int N) {
            this.N = N;
            sTree = new int[N << 1];
            lazy = new int[N << 1];
            Arrays.fill(lazy, -1);
        }

        void update_point(int index, int val) {
            index += N - 1;
            sTree[index] = val;
            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;

        }
    }
}