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.math.*;
import java.util.*;

public class CODEFORCES
{
	@SuppressWarnings("rawtypes")
	static InputReader in;
	static PrintWriter out;

	public static class SegmentTree
	{
		int n;
		int arr[][];
		int k[];

		SegmentTree(int n)
		{
			arr = new int[n << 2][26];
			k = new int[n << 2];
		}

		SegmentTree(int a[][])
		{
			this.n = a.length;
			arr = new int[n << 2][26];
			k = new int[n << 2];
			Arrays.fill(k, -1);
			build(0, n - 1, 0, a);
		}

		void build(int l, int r, int c, int a[][])
		{
			if (l == r)
			{
				arr[c] = a[l];
				return;
			}
			int mid = l + r >> 1;
			build(l, mid, (c << 1) + 1, a);
			build(mid + 1, r, (c << 1) + 2, a);
			arr[c] = merge(arr[(c << 1) + 1], arr[(c << 1) + 2]);
		}

		int[] merge(int a[], int b[])
		{
			int c[] = new int[26];
			for (int i = 0; i < 26; i++)
				c[i] = a[i] + b[i];
			return c;
		}

		int lazymerge(int a, int b)
		{
			return a + b;
		}

		boolean getInitialValue(int a)
		{
			return !(a == -1);
		}

		int[] put(int a[], int k, int len)
		{
			int u[] = new int[26];
			if (k == 1)
			{
				for (int i = 0; i < 26; i++)
				{
					int pl = Math.min(a[i], len);
					u[i] = pl;
					len -= pl;
					a[i] -= pl;
				}
			} else
			{
				for (int i = 25; i >= 0; i--)
				{
					int pl = Math.min(a[i], len);
					u[i] = pl;
					len -= pl;
					a[i] -= pl;
				}
			}
			return u;
		}

		void check(int c, int l, int r)
		{
			if (getInitialValue(k[c]))
			{
				if (l != r)
				{
					int mid = l + r >> 1;
					arr[(c << 1) + 1] = put(arr[c], k[c], mid - l + 1);
					arr[(c << 1) + 2] = put(arr[c], k[c], r - mid);
					for (int i = 0; i < 26; i++)
						arr[c][i] = arr[2 * c + 1][i] + arr[2 * c + 2][i];
					k[(c << 1) + 1] = k[c];
					k[(c << 1) + 2] = k[c];
				}
				k[c] = -1;
			}
		}

		void update(int l, int r, int c, int x, int y, int val, int op[])
		{
			check(c, l, r);
			if (l > r || x > y || l > y || x > r)
				return;
			if (x <= l && y >= r)
			{
				k[c] = val;
				if (val == 1)
				{
					int len = r - l + 1;
					for (int i = 0; i < 26; i++)
					{
						int pl = Math.min(op[i], len);
						arr[c][i] = pl;
						len -= pl;
						op[i] -= pl;
					}
				} else
				{
					int len = r - l + 1;
					for (int i = 25; i >= 0; i--)
					{
						int pl = Math.min(op[i], len);
						arr[c][i] = pl;
						len -= pl;
						op[i] -= pl;
					}
				}
				return;
			}
			int mid = l + r >> 1;
			update(l, mid, (c << 1) + 1, x, y, val, op);
			update(mid + 1, r, (c << 1) + 2, x, y, val, op);
			arr[c] = merge(arr[(c << 1) + 1], arr[(c << 1) + 2]);
		}

		void up(int x, int y, int val, int arr[])
		{
			update(0, n - 1, 0, x, y, val, arr);
		}

		int[] make(int a[])
		{
			int u[] = new int[26];
			for (int i = 0; i < 26; i++)
				u[i] = a[i];
			return u;
		}

		int[] get(int l, int r, int c, int x, int y)
		{
			check(c, l, r);
			if (l > r || x > y || l > y || x > r) // return inverse value
				return new int[26];
			else if (x <= l && y >= r)
			{
				return make(arr[c]);
			}
			int mid = l + r >> 1;
			return merge(get(l, mid, (c << 1) + 1, x, y), get(mid + 1, r, (c << 1) + 2, x, y));
		}

		int[] ans(int x, int y)
		{
			return get(0, n - 1, 0, x, y);
		}
	}

	static int value(int a[])
	{
		for (int i = 0; i < 26; i++)
			if (a[i] != 0)
				return i;
		return -1;
	}

	static void solve()
	{
		int n = in.ni(), q = in.ni();
		String a = in.readString();
		int b[][] = new int[n][26];
		for (int i = 0; i < n; i++)
			b[i][a.charAt(i) - 'a']++;
		SegmentTree s = new SegmentTree(b);
		// debug(s.ans(0, n - 1));
		while (q-- > 0)
		{
			int x = in.ni() - 1, y = in.ni() - 1, k = in.ni();
			int tmp[] = s.ans(x, y);
			// debug(tmp);
			s.up(x, y, k, tmp);
		}
		for (int i = 0; i < n; i++)
			out.print((char) ('a' + value(s.ans(i, i))));
	}

	@SuppressWarnings("rawtypes")
	static void soln()
	{
		in = new InputReader(System.in);
		out = new PrintWriter(System.out);
		solve();
		out.flush();
	}

	static void debug(Object... o)
	{
		System.out.println(Arrays.deepToString(o));
	}

	public static void main(String[] args)
	{
		new Thread(null, new Runnable()
		{
			public void run()
			{
				try
				{
					soln();
				} catch (Exception e)
				{
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
	}

	// To Get Input
	// Some Buffer Methods
	static class InputReader<SpaceCharFilter>
	{

		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream)
		{
			this.stream = stream;
		}

		public int snext()
		{
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars)
			{
				curChar = 0;
				try
				{
					snumChars = stream.read(buf);
				} catch (IOException e)
				{
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int ni()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nl()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int[] nextIntArray(int n)
		{
			int a[] = new int[n];
			for (int i = 0; i < n; i++)
			{
				a[i] = ni();
			}
			return a;
		}

		public long[] nextLongArray(int n)
		{
			long a[] = new long[n];
			for (int i = 0; i < n; i++)
			{
				a[i] = nl();
			}
			return a;
		}

		public String readString()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine()
		{
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = snext();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c)
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c)
		{
			return c == '\n' || c == '\r' || c == -1;
		}

		public interface SpaceCharFilter
		{
			public boolean isSpaceChar(int ch);
		}

	}
}