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 MainE {
	static StdIn in = new StdIn();
	static PrintWriter out = new PrintWriter(System.out);
	
	public static void main(String[] args) {
		int n=in.nextInt(), q=in.nextInt();
		char[] s = in.next().toCharArray();
		SegTree[] trees = new SegTree[26];
		for(int i=0; i<26; ++i)
			trees[i] = new SegTree(n);
		for(int i=0; i<n; ++i)
			trees[s[i]-'a'].upd(i, i, 1);
		while(q-->0) {
			int l=in.nextInt()-1, r=in.nextInt()-1, k=in.nextInt();
			int[] cnt = new int[26];
			for(int i=0; i<26; ++i) {
				cnt[i]=trees[i].get(l, r);
				trees[i].upd(l, r, 0);
			}
			if(k==1)
				for(int i=0; i<26; l+=cnt[i], ++i)
					trees[i].upd(l, l+cnt[i]-1, 1);
			else
				for(int i=0; i<26; r-=cnt[i], ++i)
					trees[i].upd(r-cnt[i]+1, r, 1);
		}
		for(int i=0; i<26; ++i)
			for(int j=0; j<n; ++j)
				if(trees[i].get(j, j)>0)
					s[j]=(char)(i+'a');
		out.println(s);
		out.close();
	}
	
	static class SegTree {
		static final int id1=-1, id2=0;
		int op2Node(int i, int len) {
			//Write fast version of:
			/*int dt=id2;
			for(int i=0; i<len; ++i)
				dt=op2(dt, d[i]);
			return op1(a[i], dt)*/
			if(d[i]==-1) {
				int d1 = -1;
				return d1==-1?a[i]:d1;
			}
			int d2 = d[i]*len;
			return d2==-1?a[i]:d2;
		}
		int n, l1, r1;
		int[] a, d;
		SegTree(int n) {
			this.n=n;
			a = new int[4*n];
			Arrays.fill(a, id2);
			d = new int[4*n];
			Arrays.fill(d, id1);
		}
		void push(int i, int l2, int r2) {
			a[i]=op2Node(i, r2-l2+1);
			if(l2<r2) {
				int d1 = d[i];
				d[2*i]=d1==-1?d[2*i]:d1;
				int d2 = d[i];
				d[2*i+1]=d2==-1?d[2*i+1]:d2;
			}
			d[i]=id1;
		}
		void upd(int l, int r, int d) {
			if(l>r)
				return;
			l1=l;
			r1=r;
			upd2(1, 0, n-1, d);
		}
		private void upd2(int i, int l2, int r2, int d2) {
			if(l1<=l2&&r2<=r1) {
				d[i]=d2==-1?d[i]:d2;
				push(i, l2, r2);
			} else {
				int mid=(l2+r2)/2;
				push(2*i, l2, mid);
				push(2*i+1, mid+1, r2);
				if(l1<=mid)
					upd2(2*i, l2, mid, d2);
				if(mid<r1)
					upd2(2*i+1, mid+1, r2, d2);
				a[i]=a[2*i]+a[2*i+1];
			}
		}
		int get(int l, int r) {
			l1=l;
			r1=r;
			return get2(1, 0, n-1);
		}
		private int get2(int i, int l2, int r2) {
			push(i, l2, r2);
			if(l1<=l2&&r2<=r1)
				return a[i];
			int mid=(l2+r2)/2;
			int res=id2;
			if(l1<=mid)
				res=get2(2*i, l2, mid)+res;
			if(mid<r1)
				res=get2(2*i+1, mid+1, r2)+res;
			return res;
		}
	}
	
	interface Input {
		public String next();
		public String nextLine();
		public int nextInt();
		public long nextLong();
		public double nextDouble();
	}
	static class StdIn implements Input {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;
		public StdIn() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
		public StdIn(InputStream in) {
			try{
				din = new DataInputStream(in);
			} catch(Exception e) {
				throw new RuntimeException();
			}
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
		public String next() {
			int c;
			while((c=read())!=-1&&(c==' '||c=='\n'||c=='\r'));
			StringBuilder s = new StringBuilder();
			while (c != -1)
			{
				if (c == ' ' || c == '\n'||c=='\r')
					break;
				s.append((char)c);
				c=read();
			}
			return s.toString();
		}
		public String nextLine() {
			int c;
			while((c=read())!=-1&&(c==' '||c=='\n'||c=='\r'));
			StringBuilder s = new StringBuilder();
			while (c != -1)
			{
				if (c == '\n'||c=='\r')
					break;
				s.append((char)c);
				c = read();
			}
			return s.toString();
		}
		public int nextInt() {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				ret = ret * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}
		public int[] readIntArray(int n) {
			int[] ar = new int[n];
			for(int i=0; i<n; ++i)
				ar[i]=nextInt();
			return ar;
		}
		public long nextLong() {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				ret = ret * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}
		public long[] readLongArray(int n) {
			long[] ar = new long[n];
			for(int i=0; i<n; ++i)
				ar[i]=nextLong();
			return ar;
		}
		public double nextDouble() {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				ret = ret * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');
			if (c == '.')
				while ((c = read()) >= '0' && c <= '9')
					ret += (c - '0') / (div *= 10);
			if (neg)
				return -ret;
			return ret;
		}
		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}
		private byte read() {
			try{
				if (bufferPointer == bytesRead)
					fillBuffer();
				return buffer[bufferPointer++];
			} catch(IOException e) {
				throw new RuntimeException();
			}
		}
		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}
}