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 ASimpleTask {
	static PrintWriter pw;
	public static int[] sumArrays(int[] a, int[] b)
	{
		int[] c = new int[26];
		for (int i = 0; i < c.length; i++) {
			c[i]=a[i]+b[i];
		}
		return c;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		String s = br.readLine();
		int N=1;
		while(N<n)
		{
			N*=2;
		}
		char[] a = new char[N+1];
		for (int i = 1; i < n+1; i++) {
			a[i]=s.charAt(i-1);
		}
		segmentTree sTree = new segmentTree(a);
		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());
			int I=Integer.parseInt(st.nextToken());
			int J=Integer.parseInt(st.nextToken());
			int K=Integer.parseInt(st.nextToken());
			int[] lettersCount=new int[26];
			for (int l = 0; l < lettersCount.length; l++) {
				lettersCount[l]=sTree.query(I, J,l);
				sTree.updateRange(I, J, 0,l);
			}
			int rangeStart=I;
			if(K==1)
			{
				for (int l = 0; l < lettersCount.length; l++) {
					if(lettersCount[l]!=0){sTree.updateRange(rangeStart, rangeStart+lettersCount[l]-1, 1, l);rangeStart+=(lettersCount[l]);}
				}
			}
			else if(K==0)
			{
				for (int l = lettersCount.length-1; l > -1; l--) {
					if(lettersCount[l]!=0){sTree.updateRange(rangeStart, rangeStart+lettersCount[l]-1, 1, l);rangeStart+=(lettersCount[l]);}
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < 26; j++) {
				if(sTree.query(i, i, j)==1){char c='a'; c+=j;pw.print(c);}
			}
		}
		pw.close();
	}
	static class segmentTree{
		 char[] a;
		 int[][]segmentTree, lazy;
		 int N;
		public segmentTree(char[] a) {
			this.a=a;
			N=a.length-1;
			segmentTree= new int[2*N][26];
			lazy= new int[2*N][26];
			for (int i = 0; i < lazy.length; i++) {
				Arrays.fill(lazy[i], -1);
			}
			build(1,1,N);
		}
		public void build(int indx, int l, int r)
		{
			if(l==r && 'a'<=a[l] && a[l]<='z'){segmentTree[indx][a[l]-'a']=1;return;}
			if(l==r)return;
			int mid=l+r>>1;
			int leftChild=indx<<1;
			int rightChild=indx<<1|1;
			build(leftChild,l,mid);
			build(rightChild, mid+1, r);
			segmentTree[indx]=sumArrays(segmentTree[leftChild],segmentTree[rightChild]);	
		}
		public int query(int i,int j, int letter)
		{
			return query(1, 1, N, i, j, letter);
		}
		public int query(int indx, int l, int r, int i, int j, int letter)
		{
			if(r<i || j<l) return 0;
			if(i<=l && r<=j)return segmentTree[indx][letter];
			int mid=l+r>>1;
			int leftChild=indx<<1;
			int rightChild=indx<<1|1;
			propagate(indx, l, r, letter);
			return query(leftChild, l, mid, i, j,letter) + query(rightChild, mid+1, r, i, j,letter);
		}
		public void updateRange(int i, int j, int val, int letter)
		{
			updateRange(1, 1, N, i, j, val, letter);
		}
		public void updateRange(int indx, int l, int r, int i, int j, int val, int letter)
		{
			if(r<i || j<l) return;
			if(i<=l && r<=j)
			{
				segmentTree[indx][letter]=(r-l+1)*val;
				lazy[indx][letter]=val; 
				return;
			}
			int mid=l+r>>1;
			int leftChild=indx<<1;
			int rightChild=indx<<1|1;
			propagate(indx,l,r,letter);
			updateRange(leftChild, l, mid, i, j, val, letter);
			updateRange(rightChild, mid + 1, r, i, j, val, letter);
			segmentTree[indx][letter]=segmentTree[leftChild][letter] + segmentTree[rightChild][letter];
		}
		public void propagate(int indx,int l, int r, int letter)
		{
			if(lazy[indx][letter]!=-1)
			{
				int mid=l+r>>1;
				int leftChild=indx<<1;
				int rightChild=indx<<1|1;
				segmentTree[leftChild][letter]=(mid-l+1)*lazy[indx][letter];
				segmentTree[rightChild][letter]=(r-mid)*lazy[indx][letter];
				lazy[leftChild][letter]=lazy[indx][letter];
				lazy[rightChild][letter]=lazy[indx][letter];
				lazy[indx][letter]=-1;
			}
		}
	}
}