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 Solution {
    int n;

    public void solve(FastScanner in, PrintWriter out) throws IOException {
        n = in.nextInt();
        int q = in.nextInt();
        String s = in.next();

        byte[] sb = new byte[n];
        for (int i = 0; i < n; i++) {
            sb[i] = (byte) (s.charAt(i) - 'a');
        }

        int[][] trees = new int[26][4 * n];
        for (byte letter = 0; letter < 26; letter++) {
            Arrays.fill(trees[letter], 0);
        }

        build(trees, sb, 0, 0, n - 1);

        int[] cnt = new int[26];
        for (int l = 0; l < q; l++) {
            int i = in.nextInt() - 1;
            int j = in.nextInt() - 1;
            int k =  in.nextInt();

            for (byte letter = 0; letter < 26; letter++) {
                cnt[letter] = getLetterTotalInTheRange(trees[letter], 0, 0, n - 1, i, j);
                if (cnt[letter] > 0) {
                    update(trees[letter], 0, 0, n - 1, i, j, (byte) 0);
                }
            }

            int start = (k == 1) ? i : j;
            int current = start;
            for (byte letter  = 0; letter < 26; letter++) {
                if (cnt[letter] == 0) {
                    continue;
                }

                int leftLimit, rightLimit;
                if (k == 1) {
                    leftLimit = current;
                    rightLimit = current + cnt[letter] - 1;
                    current = rightLimit + 1;
                } else {
                    rightLimit = current;
                    leftLimit = current - cnt[letter] + 1;
                    current = leftLimit - 1;
                }
                update(trees[letter], 0, 0, n - 1, leftLimit, rightLimit, (byte) 1);
//                for (int index = leftLimit; index <= rightLimit; index++) {
//                    sb[index] = letter;
//                }
            }
        }

        for (byte letter = 0; letter < 26; letter++) {
            copy_presence(trees[letter], 0, 0, n - 1, sb, (byte) (letter + 'a'));
        }

        out.println(new String(sb));
    }

    protected void build(int[][] trees, byte[] sb, int treeCurrIndex, int sbLeft, int sbRight)
    {
        if (sbLeft == sbRight) {
            byte letter = sb[sbLeft];
            trees[letter][treeCurrIndex] = 1;
            return;
        }

        int treeLeftIndex = treeCurrIndex * 2 + 1;
        int treeRightIndex = treeCurrIndex * 2 + 2;
        build(trees, sb, treeLeftIndex, sbLeft, (sbLeft + sbRight) / 2);
        build(trees, sb, treeRightIndex, (sbLeft + sbRight) / 2 + 1, sbRight);

        for (int i = 0; i < 26; i++) {
            trees[i][treeCurrIndex] = trees[i][treeLeftIndex] + trees[i][treeRightIndex];
        }
    }

    protected int getLetterTotalInTheRange(int[] tree, int treeCurrIndex, int sbLeft, int sbRight, int i, int j)
    {
        if ((sbLeft > j) || (sbRight < i)) {
            return 0;
        }

        int treeLeftIndex = treeCurrIndex * 2 + 1;
        int treeRightIndex = treeCurrIndex * 2 + 2;

        int stored = tree[treeCurrIndex];
        if (stored < 0) {
            tree[treeCurrIndex] = (-stored - 1) * (sbRight - sbLeft + 1);
            if (sbLeft != sbRight) {
                tree[treeLeftIndex] = stored;
                tree[treeRightIndex] = stored;
            }
        }

        if ((sbLeft >= i) && (sbRight <= j)) {
            return tree[treeCurrIndex];
        }

        int numLeft = getLetterTotalInTheRange(tree, treeLeftIndex, sbLeft, (sbLeft + sbRight) / 2, i, j);
        int numRight = getLetterTotalInTheRange(tree, treeRightIndex, (sbLeft + sbRight) / 2 + 1, sbRight, i, j);
        return numLeft + numRight;
    }

    protected int update(int[] tree, int treeCurrIndex, int sbLeft, int sbRight, int i, int j, byte val)
    {
        if ((sbLeft > j) || (sbRight < i)) {
            int stored = tree[treeCurrIndex];
            if (stored < 0) {
                stored = (-stored - 1) * (sbRight - sbLeft + 1);
            }
            return stored;
        }

        int treeLeftIndex = treeCurrIndex * 2 + 1;
        int treeRightIndex = treeCurrIndex * 2 + 2;

        if ((sbLeft >= i) && (sbRight <= j)) {
            tree[treeCurrIndex] = val * (sbRight - sbLeft + 1);
            if (sbLeft != sbRight) {
                tree[treeLeftIndex] = -val - 1;
                tree[treeRightIndex] = -val - 1;
            }
            return tree[treeCurrIndex];
        }

        int stored = tree[treeCurrIndex];
        if (stored < 0) {
            tree[treeLeftIndex] = stored;
            tree[treeRightIndex] = stored;
        }

        tree[treeCurrIndex] = update(tree, treeLeftIndex, sbLeft, (sbLeft + sbRight) / 2, i, j, val)
                + update(tree, treeRightIndex, (sbLeft + sbRight) / 2 + 1, sbRight, i, j, val);

        return tree[treeCurrIndex];
    }

    protected void copy_presence(int[] tree, int treeCurrIndex, int sbLeft, int sbRight, byte[] sb, byte letter)
    {
        int stored = tree[treeCurrIndex];
        if (stored < 0) {
            stored = (-stored - 1) * (sbRight - sbLeft + 1);
        }

        if (stored == 0) {
            return;
        }
        if (stored == (sbRight - sbLeft + 1)) {
            for (int i = sbLeft; i <= sbRight; i++) {
                sb[i] = letter;
            }
            return;
        }

        int treeLeftIndex = treeCurrIndex * 2 + 1;
        int treeRightIndex = treeCurrIndex * 2 + 2;
        copy_presence(tree, treeLeftIndex, sbLeft, (sbLeft + sbRight) / 2, sb, letter);
        copy_presence(tree, treeRightIndex, (sbLeft + sbRight) / 2 + 1, sbRight, sb, letter);
    }

    // --------Misc code - streams creation, tests, etc.----------------------------------------------------
    public void run() {
        try {
            if (System.getProperty("ONLINE_JUDGE") != null) {
                this.runConsoleInput();
            } else {
                this.runFromInputFiles();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    protected void runFromInputFiles() throws IOException {
        ArrayList<File> files = new ArrayList<>();
        for (int i = 0; true; i++) {
            File file = new File("test" + (i + 1) + ".txt");
            if (!file.exists()) {
                break;
            }
            files.add(file);
        }

        PrintWriter out = new PrintWriter(System.out);
        for (int i = 0; i < files.size(); i++) {
            out.println("=========Test " + (i + 1) + "=========");
            FastScanner in = new FastScanner(new FileInputStream(files.get(i)));
            solve(in, out);

            String token;
            while ((token = in.next()) != null) {
                out.print(token + " ");
            }
            out.println("");
        }
        out.close();
    }

    protected void runConsoleInput() throws IOException {
        FastScanner in = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        solve(in, out);

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream), 32768);
        }

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

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

    public static void main(String[] arg) {
        new Solution().run();
    }
}