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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author skt
 */
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);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskE {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        int q = in.nextInt();
        String S = in.next();
        SegmentTree[] trees = new SegmentTree[26];
        for (int i = 0; i < 26; i ++) {
            trees[i] = new SegmentTree(n);
            trees[i].build(1, n, 1);
        }
        for (int i = 0; i < n; i ++) {
            int x = (int)(S.charAt(i) - 'a');
            trees[x].update(i + 1, i + 1, 1, n, 1, 1);

        }
        for (int i = 0; i < q; i ++) {
            int l, r, type;
            l = in.nextInt();
            r = in.nextInt();
            type = in.nextInt();
            if (type == 1) {
                int start = l;
                for (int j = 0; j <= 25; j ++) {
                    int cnt = trees[j].query(l, r, 1, n, 1);
                    if (cnt > 0) {
                        trees[j].update(l, r, 1, n, 1, 0);
                        trees[j].update(start, start + cnt - 1, 1, n, 1, 1);
                        start += cnt;
                    }
                }
            } else {
                int start = l;
                for (int j = 25; j >= 0; j --) {
                    int cnt = trees[j].query(l, r, 1, n, 1);
                    if (cnt > 0) {
                        trees[j].update(l, r, 1, n, 1, 0);
                        trees[j].update(start, start + cnt - 1, 1, n, 1, 1);
                        start += cnt;
                    }
                }
            }
        }
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < 26; j ++) {
                int c = trees[j].query(i + 1, i + 1, 1, n, 1);
                if (c > 0) {
                    out.print((char)('a' + j));
                }
            }
        }
        out.println();
    }
}

class SegmentTree {
    int[] c, l, r;

    public SegmentTree(int n) {
        c = new int[n * 4];
        l = new int[n * 4];
        r = new int[n * 4];
    }

    public void build(int l, int r, int pos) {
        this.l[pos] = l;
        this.r[pos] = r;
        if (l == r) {
            return ;
        }
        int mid = (l + r) >> 1;
        build(l, mid, lson(pos));
        build(mid + 1, r, rson(pos));
    }

    public void update(int l, int r, int L, int R, int pos, int op) {
        if (l <= L && R <= r) {
            if (op == 0) {
                c[pos] = 0;
            } else {
                c[pos] = R - L + 1;
            }
            return ;
        }
        pushdown(pos);
        int mid = (L + R) >> 1;
        if (mid >= l) {
            update(l, r, L, mid, lson(pos), op);
        }
        if (mid < r) {
            update(l, r, mid + 1, R, rson(pos), op);
        }
        pushup(pos);
    }

    public int query(int l, int r, int L, int R, int pos) {
        if (l <= L && R <= r) {
            return c[pos];
        }
        pushdown(pos);
        int mid = (L + R) >> 1, ans = 0;
        if (mid >= l) {
            ans += query(l, r, L, mid, lson(pos));
        }
        if (mid < r) {
            ans += query(l, r, mid + 1, R, rson(pos));
        }
        pushup(pos);
        return ans;
    }

    public int lson(int pos) {
        return (pos << 1);
    }

    public int rson(int pos) {
        return (pos << 1) | 1;
    }

    public void pushup(int pos) {
        c[pos] = c[lson(pos)] + c[rson(pos)];
    }

    public void pushdown(int pos) {
        if (c[pos] == 0) {
            c[lson(pos)] = 0;
            c[rson(pos)] = 0;
        } else if (c[pos] == r[pos] - l[pos] + 1) {
            c[lson(pos)] = r[lson(pos)] - l[lson(pos)] + 1;
            c[rson(pos)] = r[rson(pos)] - l[rson(pos)] + 1;
        }
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

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

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

}