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

/**
 * 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);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    private String s;
    int n, q;
    private int[][] it, change;
    private int[] a, cnt;

    private void Build(int id, int i, int l, int r) {
        change[id][i] = -1;
        if (l == r) {
            it[id][i] = (a[l] == id ? 1 : 0);
            return;
        }
        int mid = (l + r) >> 1;
        Build(id, i + i, l, mid);
        Build(id, i + i + 1, mid + 1, r);
        it[id][i] = it[id][i + i] + it[id][i + i + 1];
    }

    private void Update(int id, int i, int l, int r, int value) {
        it[id][i] = (r - l + 1) * value;
        change[id][i] = value;
    }

    private int GetChar(int id, int i, int l, int r, int u, int v) {
        if (l > v || r < u) return 0;
        if (l >= u && r <= v)
            return it[id][i];
        int mid = (l + r) >> 1;
        if (change[id][i] >= 0) {
            Update(id, i + i, l, mid, change[id][i]);
            Update(id, i + i + 1, mid + 1, r, change[id][i]);
            change[id][i] = -1;
        }
        it[id][i] = it[id][i + i] + it[id][i + i + 1];
        return GetChar(id, i + i, l, mid, u, v) + GetChar(id, i + i + 1, mid + 1, r, u, v);
    }

    private void Update(int id, int i, int l, int r, int u, int v, int value) {
        if (l > v || r < u || l > r) return;
        if (l >= u && r <= v) {
            it[id][i] = value * (r - l + 1);
            change[id][i] = value;
            return;
        }
        int mid = (l + r) >> 1;
        if (change[id][i] >= 0) {
            Update(id, i + i, l, mid, change[id][i]);
            Update(id, i + i + 1, mid + 1, r, change[id][i]);
            change[id][i] = -1;
        }
        Update(id, i + i, l, mid, u, v, value);
        Update(id, i + i + 1, mid + 1, r, u, v, value);
        it[id][i] = it[id][i + i] + it[id][i + i + 1];
    }

    private void FindRes(int id, int i, int l, int r) {
        if (it[id][i] == 0) return;
        if (l == r) {
            a[l] = id;
            return;
        }
        int mid = (l + r) >> 1;
        if (change[id][i] >= 0) {
            Update(id, i + i, l, mid, change[id][i]);
            Update(id, i + i + 1, mid + 1, r, change[id][i]);
            change[id][i] = -1;
        }
        FindRes(id, i + i, l, mid);
        FindRes(id, i + i + 1, mid + 1, r);
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        n = in.nextInt();
        q = in.nextInt();
        s = in.nextLine();
        a = new int[n + 1];
        for (int i = 0; i < n; ++i)
            a[i + 1] = (int) s.charAt(i) - (int) 'a';

        it = new int[26][n * 8];
        change = new int[26][n * 8];

        for (int i = 0; i < 26; ++i)
            Build(i, 1, 1, n);

        cnt = new int[26];
        while (q-- > 0) {
            int l = in.nextInt(), r = in.nextInt(), up = in.nextInt();
            Arrays.fill(cnt, 0);
            for (int i = 0; i < 26; ++i) {
                cnt[i] = GetChar(i, 1, 1, n, l, r);
                Update(i, 1, 1, n, l, r, 0);
            }
            if (up == 0) {
                int pos = r;
                for (int i = 0; i < 26; ++i) {
                    Update(i, 1, 1, n, pos - cnt[i] + 1, pos, 1);
                    pos -= cnt[i];
                }

            } else {
                int pos = l;
                for (int i = 0; i < 26; ++i) {
                    Update(i, 1, 1, n, pos, pos + cnt[i] - 1, 1);
                    pos += cnt[i];
                }
            }
        }

        for (int i = 0; i < 26; ++i)
            FindRes(i, 1, 1, n);

        for(int i = 1; i <= n; ++i) out.print((char) (a[i] + (int) 'a'));
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

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

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

    public String nextLine() {
        try {
            String line = reader.readLine();
            if (line == null)
                throw new UnknownError();
            return line;
        } catch (Exception e) {
            throw new UnknownError(e.getMessage());
        }
    }

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

}