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

public class Main2 {
	public static void main(String[] args) throws Throwable 
	{
		Scanner sc = new Scanner((System.in));
		int n = sc.nextInt();
		int q = sc.nextInt();
		char[] arr = sc.nextLine().toCharArray();
		SegmentTree[] tree = new SegmentTree[26];
		for (int i = 0; i < tree.length; i++) 
			tree[i] = new SegmentTree(arr, (char) (i+'a'));
		
		while(q-->0)
		{
			int l = sc.nextInt()  , r = sc.nextInt()  , k = sc.nextInt();
			if(k==1)
			{
				int ind = l;
				for (int i = 0; i < 26; i++) 
				{
					int total = tree[i].query(l, r);
					
					tree[i].update(l, r, -1);
					tree[i].update(ind, ind+total-1, 1);
					ind += total;
				}
			}
			else
			{
				int ind = l;
				for (int i = 25; i >= 0; i--) 
				{
					int total = tree[i].query(l, r);
					
					tree[i].update(l, r, -1);
					tree[i].update(ind, ind+total-1, 1);
					ind += total ;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0;i < n;i++)		
			for(int j = 0 ; j<26;j++)		
				if(tree[j].query(i+1, i+1)==1)			
					sb.append((char)(j+'a'));
				
		System.out.println(sb);
		
	}	
	
	static class SegmentTree
	{
		int n , arr[] , lazy[];
		char in[];
		public SegmentTree(char[] i,char c) {
			n = i.length;
			arr = new int[n<<2];
			lazy = new int[n<<2];
			in = i;
			build(1,1,n,c);
		}
		int left(int cur){return cur<<1;}
		int right(int cur){return cur<<1|1;}
		
		void build(int cur,int l,int r,char c)
		{
			if(l==r)arr[cur] = in[l-1]==c? 1 : 0;
			else
			{
				int mid = (l+r)>>1;
				build(left(cur), l, mid, c);
				build(right(cur), mid+1, r, c);
				arr[cur] = arr[left(cur)] + arr[right(cur)];
			}
		}
		
		void update(int l,int r,int val) // value:  1->Set ||| 0->Hold ||| -1->Reset 
		{
			update(1, 1, n, l, r, val);
		}
		
		void update(int cur,int l,int r,int lq,int rq,int val)
		{
			propagate(cur, l, r);
			if(l>rq || r<lq)return;
			if(l>=lq && r<=rq)
			{
				lazy[cur] = val;
				propagate(cur, l, r);
			}
			else
			{
				int mid = (l+r)>>1;
				update(left(cur), l, mid, lq, rq, val);
				update(right(cur), mid+1, r, lq, rq, val);
				arr[cur] = arr[left(cur)] + arr[right(cur)];
			}
		}
		
		void propagate(int cur,int l,int r)
		{
			if(lazy[cur]==0)return;
			if(lazy[cur]==1) arr[cur] = r-l+1;
			else arr[cur] = 0;
			if(l!=r)
			{
				lazy[left(cur)] = lazy[cur];
				lazy[right(cur)] = lazy[cur];
			}
			lazy[cur] = 0;
		}
		
		int query(int lq,int rq)
		{
			return query(1, 1, n, lq, rq);
		}
		
		int query(int cur,int l,int r,int lq,int rq)
		{
			propagate(cur, l, r);
			if(l>rq || r<lq)return 0;
			if(l>=lq && r<=rq)return arr[cur];
			int mid = (l+r)>>1;
			return query(left(cur), l, mid, lq, rq) + query(right(cur), mid+1, r, lq, rq);
		}
	}
	
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;
		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}		
		public long nextLong() throws NumberFormatException, IOException {return Long.parseLong(next());}
		public Scanner(FileReader r){	br = new BufferedReader(r);}
		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		public String nextLine() throws IOException {return br.readLine();}
		public boolean ready() throws IOException {return br.ready();}
	}
}