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

public class A {

	static char[] s;

	public static void main(String[] args) throws IOException 
	{
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n = sc.nextInt(), q = sc.nextInt();
		s = sc.next().toCharArray();
		TreeMap<Integer, Interval> map = new TreeMap<>();
		map.put(0, new Interval(0, n - 1));
		while(q-->0)
		{
			int i = sc.nextInt() - 1, j = sc.nextInt() - 1, k = sc.nextInt();
			Integer key = map.lowerKey(i);
			Interval x = new Interval(k, i, j);
			if(key != null)
			{
				Interval before = map.get(key);
				if(before.r >= i)
				{
					if(before.r <= j)
						before.cutRight(x);				
					else if(before.k == -1)
					{
						map.put(j + 1, new Interval(j + 1, before.r));
						before.r = j;
						before.cutRight(x);
					}
					else
					{
						Interval y = new Interval(before.k, i, before.r);
						before.cutRight(y);
						y.cutLeft(x);
						map.put(j + 1, y);
					}
				}
			}
			while(true)
			{
				key = map.ceilingKey(i);
				if(key == null)
					break;
				Interval after = map.get(key);
				if(after.l > x.r)
					break;
				map.remove(key);
				if(after.r <= x.r)
					after.merge(x);
				else
				{
					after.cutLeft(x);
					map.put(after.l, after);
				}
			}
			map.put(i, x);
		}
		StringBuilder sb = new StringBuilder();
		for(Interval i: map.values())
			sb.append(i);
		out.println(sb);
		out.flush();
		out.close();
	}

	static class Interval
	{
		int l, r, k = -1;
		int[] f;

		Interval(int x, int a, int b) { this(a, b); k = x; f = new int[26]; }

		Interval(int a, int b) { l = a; r = b; }

		void cutRight(Interval x)
		{
			int cnt = r - x.l + 1;
			if(k == -1)
			{
				for(int i = x.l; i <= r; ++i)
					x.f[s[i] - 'a']++;
			}
			else if(k == 0)
			{

				for(int i = 0; cnt > 0; ++i)
					if(f[i] != 0)
					{
						x.f[i]++;
						f[i--]--;
						--cnt;
					}
			}
			else
			{
				for(int i = 25; cnt > 0; --i)
					if(f[i] != 0)
					{
						x.f[i]++;
						f[i++]--;
						--cnt;
					}
			}
			r = x.l - 1;
		}

		void cutLeft(Interval x)
		{
			int cnt = x.r - l + 1;
			if(k == -1)
			{
				for(int i = l; i <= x.r; ++i)
					x.f[s[i] - 'a']++;
			}
			else if(k == 0)
			{
				for(int i = 25; cnt > 0; --i)
					if(f[i] != 0)
					{
						x.f[i]++;
						f[i++]--;
						--cnt;
					}
			}
			else
			{
				for(int i = 0; cnt > 0; ++i)
					if(f[i] != 0)
					{
						x.f[i]++;
						f[i--]--;
						--cnt;
					}
			}
			l = x.r + 1;
		}

		void merge(Interval x)
		{
			if(k == -1)
				for(int i = l; i <= r; ++i)
					x.f[s[i] - 'a']++;
			else
				for(int i = 0; i < 26; ++i)
					x.f[i] += f[i];
		}

		public String toString()
		{
			StringBuilder ret = new StringBuilder();
			if(k == -1)
				for(int i = l; i <= r; ++i)
					ret.append(s[i]);
			else if(k == 0)
				for(int i = 25; i >= 0; --i)
					while(f[i]-- > 0)
						ret.append((char)(i + 'a'));
			else
				for(int i = 0; i < 26; ++i)
					while(f[i]-- > 0)
						ret.append((char)(i + 'a'));
			return ret.toString();

		}
	}

	static class Scanner 
	{
		StringTokenizer st;	
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		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 long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}

		public double nextDouble() throws IOException { return Double.parseDouble(next()); }
	}
}