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.*;

public class ProblemE {
    public static void main(String[] args) {
        int testMode = 0;
        String testInput = "10 1\n" +
                "agjucbvdfk\n" +
                "1 10 1";
        /*-------------------------------------------------------------------------------------------------------*/
        FastReader in = new FastReader( System.in );
        PrintWriter out = new PrintWriter(System.out);
        new ProblemSolver().solve(in, out);
        out.close();
    }
}

class ProblemSolver {
    void solve(FastReader in, PrintWriter out) {
        int n = in.nextInt();
        int Q = in.nextInt();
        char[] s = in.nextToken().toCharArray();

        TreeMap<Integer, Integer>[] charIntervals = new TreeMap[26];
        for (int i = 'a'; i <= 'z'; i++) {
            charIntervals[i - 'a'] = new TreeMap<>();
            for (int k = 0; k < n; k++) {
                int j = 0;
                while (k + j < n && s[k + j] == i) j++;
                if (j > 0) charIntervals[i - 'a'].put(k, k + j - 1);
                k += j;
            }
        }


        for (int q = 0; q < Q; q++) {
            int l = in.nextInt() - 1;
            int r = in.nextInt() - 1;
            int t = in.nextInt();
            int off = 0;
            for (int i = (t > 0 ? 0 : 25); i != (t > 0 ? 26 : -1); ) {
                int chars = 0;
                Map.Entry<Integer, Integer> e = charIntervals[i].floorEntry(l);
                if (e == null && charIntervals[i].size() > 0) {
                    if (l < charIntervals[i].firstKey()) e = charIntervals[i].firstEntry();
                }
                for (; e != null; e = charIntervals[i].higherEntry(e.getKey())) {
                    if (e.getValue() < l) continue;
                    if (r < e.getKey()) break;
                    charIntervals[i].remove(e.getKey());
                    chars += e.getValue() - e.getKey() + 1;
                    if (e.getKey() < l) {
                        chars -= (l - e.getKey());
                        charIntervals[i].put(e.getKey(), l - 1);
                    }
                    if (e.getValue() > r) {
                        chars -= (e.getValue() - r);
                        charIntervals[i].put(r + 1, e.getValue());
                    }
                }
                if (chars > 0) charIntervals[i].put(l + off, l + off + chars - 1);
                off += chars;
                i += (t > 0 ? 1 : -1);
            }
        }



        ArrayList<Interval> intervals = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            for (Map.Entry<Integer, Integer> e : charIntervals[i].entrySet()) {
                intervals.add(new Interval(e.getKey(), e.getValue(), (char) ('a' + i)));
            }
        }
        Collections.sort(intervals);
        StringBuilder sb = new StringBuilder();
        for (Interval i : intervals) {
            for (int k = i.l; k <= i.r; k++) sb.append(i.c);
        }
        out.println(sb.toString());
    }
}
class Interval implements Comparable<Interval> {
    public int l;
    public int r;
    public char c;

    public Interval(int l, int r, char c) {
        this.l = l;
        this.r = r;
        this.c = c;
    }

    public int compareTo(Interval o) {
        if (this.l < o.l) return -1;
        if (this.l == o.l) return (this.r - o.r);
        return 1;
    }
}

class FastReader extends BufferedReader {
    private StringTokenizer st;

    public FastReader(InputStream is) {
        super(new InputStreamReader(is));
    }

    public String nextToken() {
        try {
            while (st == null || !st.hasMoreElements()) {
                st = new StringTokenizer(readLine());
            }
            return st.nextToken();
        } catch (IOException e) {
            return null;
        }
    }

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

    public long nextLong() {
        return Long.parseLong(nextToken());
    }

    public int[] nextArrayInt(int size) {
        int[] ret = new int[size];
        for (int i = 0; i < size; i++) {
            ret[i] = nextInt();
        }
        return ret;
    }
}