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 treebasics;

import java.util.*;

// https://codeforces.com/contest/558/problem/E
public class ASimpleTask {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        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);
        }
        print(n, roots);
    }

    static void print(int n, SegTree[] roots) {
        char[] arr = new char[n];
        for(int i = 0; i < n; i++) {
//            boolean taken = false;
            for (int c = 0; c < 26; c++) {
                if (roots[c].count(i,i) > 0) {
//                    if (taken) {
//                        throw new IllegalStateException(String.format(
//                                "position %d occupied by %c and %c", i,'a'+c,arr[i]));
//                    }
//                    taken = true;
                    arr[i] = (char) ('a' + c);
                    break;
                }
            }
        }
        System.out.println(new String(arr));
    }

    static class SegTree {
        int a, b;
        int sum;
        int set = -1;
        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]
                    if (l > a) {
                        if(l <= mid+1) {
                            leftChild.set(a, l - 1, set);
                        } else {
                            leftChild.set(a,mid,set);
                            rightChild.set(mid+1, l-1, set);
                        }
                    }
                    if(r < b) {
                        if(r >= mid) {
                            rightChild.set(r+1, b, set);
                        } else {
                            rightChild.set(mid+1, b, set);
                            leftChild.set(r+1, mid, set);
                        }
                    }
                    set = -1;
                }

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