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:
//package cf312;

import java.io.*;
import java.util.*;

// https://codeforces.com/contest/558/problem/E
public class E {
    public static void solve(Reader sc, PrintWriter out) {
        int n = sc.nextInt();
        int q = sc.nextInt();
        char[] arr = sc.next().toCharArray();
        SegTree[] roots = new SegTree[26];
        for (int j = 0; j < 26; j++) {
            char c = 'a';
            c += j;
            roots[j] = new SegTree(0, n-1, arr, c);
        }
        for (int i = 0; i < q; i++) {
            int l = sc.nextInt() - 1;
            int r = sc.nextInt() - 1;
            boolean increasing = sc.nextInt() == 1;

            int index = l;
            if (increasing) {
                for (int let = 0; let < 26; let++) {
                    int count = roots[let].count(l, r);
                    if (count > 0) {
                        roots[let].set(l,r,0);
                        roots[let].set(index, index+count-1, 1);
                    }
                    index+=count;
                }
            } else {
                for (int let = 25; let >= 0; let--) {
                    int count = roots[let].count(l, r);
                    if (count > 0) {
                        roots[let].set(l,r,0);
                        roots[let].set(index, index+count-1, 1);
                    }
                    index+=count;
                }
            }
        }
        print(n, roots, out);
    }

    public static void main(String[] args) throws IOException {
        Reader in = null;
        PrintWriter out = null;
        for (String arg : args) {
            if (arg.startsWith("input")) {
                in = new Reader(arg);
            } else if (arg.startsWith("output")) {
                out = new PrintWriter(new FileWriter(arg));
            }
        }
        if (in == null) in = new Reader();
        if (out == null) out = new PrintWriter(new OutputStreamWriter(System.out));

        solve(in, out);

        out.flush();
    }

    static void print(int n, SegTree[] roots, PrintWriter out) {
        char[] arr = new char[n];
        for(int i = 0; i < n; i++) {
            for (int c = 0; c < 26; c++) {
                if (roots[c].count(i,i) > 0) {
                    arr[i] = (char) ('a' + c);
                    break;
                }
            }
        }
        out.println(new String(arr));
    }

    static class SegTree {
        final int a, b;
        int sum;
        int set = -1;
        final SegTree leftChild, rightChild;

        public SegTree(int a, int b, char[] arr, char c) {
            this.a = a;
            this.b = b;
            if (a == b) {
                leftChild = null;
                rightChild = null;
                sum = c == arr[a] ? 1 : 0;
            } else {
                int mid = (a+b)/2;
                leftChild = new SegTree(a, mid, arr, c);
                rightChild = new SegTree(mid+1, b, arr, c);
                sum = leftChild.sum + rightChild.sum;
            }
        }

        // set everything on [l, r] to 'value'
        void set(int l, int r, int value) {
            // enforce
            if (l < a || r > b) {
                throw new IllegalStateException(
                        String.format("[%d %d] out of range of [%d %d]", l,r,a,b));
            }

            if (l == a && r == b) {
                set = value; // cancel any existing 'set' order
                sum = (r - l + 1) * value;
            } else {
                int mid = (a+b)/2;

                if (set >= 0) {
                    // apply 'set' order to everything outside of [l, r]
                    int temp = set;
                    set = -1;
                    if (l > a) set(a,l-1,temp);
                    if (r < b) set(r+1,b,temp);
                }

                if (l <= mid) {
                    leftChild.set(l, Math.min(r, mid), value);
                }
                if (r > mid) {
                    rightChild.set(Math.max(mid+1, l), r, value);
                }
                sum = leftChild.sum + rightChild.sum;
            }
        }

        int count(int l, int r) {
            // enforce
            if (l < a || r > b) {
                throw new IllegalStateException(
                        String.format("[%d %d] out of range of [%d %d]", l,r,a,b));
            }

            if (l==a && r==b) {
                return sum;
            }
            if (set >= 0) {
                return (r - l + 1) * set;
            }
            int count = 0;
            int mid = (a+b)/2;
            if (l <= mid) {
                count+=leftChild.count(l, Math.min(r,mid));
            }
            if (r>mid) {
                count+=rightChild.count(Math.max(mid+1,l), r);
            }
            return count;
        }
    }
    
    static class Reader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Reader() {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
        }

        public Reader(String fileName) throws FileNotFoundException {
            reader = new BufferedReader(new FileReader(fileName));
        }

        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());
        }

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