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.InputMismatchException;
import java.io.IOException;
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;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EASimpleTask solver = new EASimpleTask();
        solver.solve(1, in, out);
        out.close();
    }

    static class EASimpleTask {
        public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            int q = in.nextInt();
            String S = in.next();

            Lazy[] alph = new Lazy[26];

            for (int i = 0; i < 26; i++) alph[i] = new Lazy(n);
            for (int i = 0; i < n; i++) {
                alph[S.charAt(i) - 'a'].upd(i, i, 1, 1, 0, n - 1);
            }

            for (int qe = 0; qe < q; qe++) {
                int l = in.nextInt() - 1;
                int r = in.nextInt() - 1;
                int k = in.nextInt();
                int[] c = new int[26];
                for (int i = 0; i < 26; i++) c[i] = alph[i].query(l, r, 1, 0, n - 1);
                if (k == 1) {
                    int cur = l;
                    for (int i = 0; i < 26; i++) {
                        if (c[i] == 0) continue;
                        alph[i].upd(l, r, 1, 0, 0, n - 1);
                        alph[i].upd(cur, cur + c[i] - 1, 1, 1, 0, n - 1);
                        cur += c[i];
                    }
                } else {
                    int cur = l;
                    for (int i = 25; i >= 0; i--) {
                        if (c[i] == 0) continue;
                        alph[i].upd(l, r, 1, 0, 0, n - 1);
                        alph[i].upd(cur, cur + c[i] - 1, 1, 1, 0, n - 1);
                        cur += c[i];
                    }
                }
            }
            char[] ans = new char[n];
            for (int i = 0; i < 26; i++) {
                alph[i].put(ans, 1, 0, n - 1, (char) (i + 'a'));
            }
            out.println(new String(ans));

        }

        class Lazy {
            int[] tree;
            int[] lazy;
            int SZ;

            Lazy(int n) {
                SZ = Integer.highestOneBit(n);
                if (SZ != n) SZ <<= 1;
                tree = new int[2 * SZ];
                lazy = new int[2 * SZ];
                Arrays.fill(lazy, -1);
            }

            void put(char[] ans, int idx, int L, int R, char c) {
                push(idx, L, R);
                if (L == R) {
                    if (tree[idx] == 1) {
                        ans[L] = c;
                    }
                } else {
                    int M = (L + R) / 2;
                    put(ans, 2 * idx, L, M, c);
                    put(ans, 2 * idx + 1, M + 1, R, c);
                }
            }

            void push(int idx, int L, int R) {
                if (lazy[idx] == -1) return;
                tree[idx] = (R - L + 1) * (lazy[idx]);
                if (L != R) {
                    lazy[2 * idx + 1] = lazy[idx];
                    lazy[2 * idx] = lazy[idx];
                }
                lazy[idx] = -1;
            }

            void pull(int idx) {
                tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
            }

            void upd(int lo, int hi, int idx, int inc, int L, int R) {
                push(idx, L, R);
                if (hi < L || R < lo) return;
                if (L >= lo && R <= hi) {
                    lazy[idx] = inc;
                    push(idx, L, R);
                    return;
                }
                int M = (L + R) / 2;
                upd(lo, hi, 2 * idx, inc, L, M);
                upd(lo, hi, 2 * idx + 1, inc, M + 1, R);
                pull(idx);
            }

            int query(int lo, int hi, int idx, int L, int R) {
                push(idx, L, R);
                if (hi < L || R < lo) return 0;
                if (L >= lo && R <= hi) return tree[idx];
                int M = (L + R) / 2;
                return query(lo, hi, 2 * idx, L, M) + query(lo, hi, 2 * idx + 1, M + 1, R);
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuffer res = new StringBuffer();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }
}