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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class COVID {

	static long mod = (int) 1e9 + 7;
	static long INF = Long.MAX_VALUE;
	static int n;
	static int[][] st, lazy;
	static boolean[][] mark;
	static char[] arr;

	public static void build() {
		st = new int[26][n << 2];
		mark = new boolean[26][n << 2];
		lazy = new int[26][n << 2];
		build(1, 1, n);
	}

	public static void build(int v, int b, int e) {
		if (b == e) {
			st[arr[b - 1] - 'a'][v] = 1;
		} else {
			int mid = b + e >> 1;
			build(v << 1, b, mid);
			build(v << 1 | 1, mid + 1, e);
			for (int i = 0; i < 26; i++)
				st[i][v] = st[i][v << 1] + st[i][v << 1 | 1];
		}
	}

	public static int query(int l, int r, int k) {
		return query(1, 1, n, l, r, k);

	}

	public static void propagate(int k, int v, int b, int e, int m) {
		if (mark[k][v]) {
			lazy[k][v << 1 | 1] = lazy[k][v << 1] = lazy[k][v];
			mark[k][v << 1] = mark[k][v << 1 | 1] = mark[k][v];

			st[k][v << 1] = (m - b + 1) * lazy[k][v];
			st[k][v << 1 | 1] = (e - m) * lazy[k][v];
			mark[k][v] = false;
		}
	}

	public static int query(int v, int b, int e, int l, int r, int k) {
		if (l > e || r < b)
			return 0;
		if (l <= b && e <= r) {
			return st[k][v];
		}
		int mid = b + e >> 1;
		propagate(k, v, b, e, mid);
		return query(v << 1, b, mid, l, r, k) + query(v << 1 | 1, mid + 1, e, l, r, k);

	}

	public static void update(int l, int r, int val, int k) {
		update(1, 1, n, l, r, val, k);
	}

	public static void update(int v, int b, int e, int l, int r, int val, int k) {
		if (l > e || r < b)
			return;
		if (l <= b && e <= r) {
			st[k][v] = (val) * (e - b + 1);
			mark[k][v] = true;
			lazy[k][v] = val;
		} else {
			int mid = b + e >> 1;
			propagate(k, v, b, e, mid);
			update(v << 1, b, mid, l, r, val, k);
			update(v << 1 | 1, mid + 1, e, l, r, val, k);
			st[k][v] = st[k][v << 1] + st[k][v << 1 | 1];
		}
	}

	static PrintWriter pw;

	public static void main(String[] args) throws Exception {

		Scanner sc = new Scanner(System.in);
		pw = new PrintWriter(System.out);
		n = sc.nextInt();
		int q = sc.nextInt();
		arr = sc.next().toCharArray();
		build();
		while (q-- > 0) {
			int l = sc.nextInt();
			int r = sc.nextInt();
			int t = sc.nextInt();
			int id = l;
			if (t == 1) {
				for (int c = 0; c < 26; c++) {
					int cnt = query(l, r, c);
					if (cnt == 0)
						continue;
					update(l, r, 0, c);
					update(id, id + cnt - 1, 1, c);
					id += cnt;
				}
			} else {

				for (int c = 25; c >= 0; c--) {
					int cnt = query(l, r, c);
					if (cnt == 0)
						continue;
					update(l, r, 0, c);
					update(id, id + cnt - 1, 1, c);
					id += cnt;
				}

			}

		}

		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < 26; j++) {
				if (query(i + 1, i + 1, j) == 1) {
					pw.print((char) ('a' + j));
					break;
				}
			}
		}

		pw.close();
	}

	static long gcd(long a, long b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static long lcm(long a, long b) {
		return a / gcd(a, b) * b;
	}

	public static int log(int n, int base) {
		int ans = 0;
		while (n + 1 > base) {
			ans++;
			n /= base;
		}
		return ans;
	}

	static int pow(int b, long e) {
		int ans = 1;
		while (e > 0) {
			if ((e & 1) == 1)
				ans = (int) ((ans * 1l * b));
			e >>= 1;
			{

			}
			b = (int) ((b * 1l * b));
		}
		return ans;
	}

	static long powmod(long b, long e, int mod) {
		long ans = 1;
		b %= mod;
		while (e > 0) {
			if ((e & 1) == 1)
				ans = (int) ((ans * 1l * b) % mod);
			e >>= 1;
			b = (int) ((b * 1l * b) % mod);
		}
		return ans;
	}

	public static long add(long a, long b) {
		return (a + b) % mod;
	}

	public static long mul(long a, long b) {
		long r = a * b;
		if (a * b >= mod)
			return r % mod;
		return r;
//		return ((a) * (b)) % mod;
	}

	static class longPair implements Comparable<longPair> {
		long x, y;

		public longPair(long a, long b) {
			x = a;
			y = b;
		}

		public int compareTo(longPair p) {
			return (p.x == x) ? ((p.y == y) ? 0 : (y > p.y) ? 1 : -1) : (x > p.x) ? 1 : -1;
		}
	}

	static class Pair implements Comparable<Pair> {

		int x;
		int y;

		public Pair(int a, int b) {
			this.x = a;
			y = b;
		}

		public int compareTo(Pair o) {
			return (x == o.x) ? ((y > o.y) ? 1 : (y == o.y) ? 0 : -1) : ((x > o.x) ? 1 : -1);
			// return y-o.y;
		}

		@Override

		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + x;
			result = prime * result + y;
			return result;
		}

		@Override

		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Pair other = (Pair) obj;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}

	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

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

		public Scanner(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(s));
		}

		public long[] nextLongArr(int n) throws IOException {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++)
				arr[i] = nextLong();
			return arr;
		}

		public int[] nextIntArr(int n) throws IOException {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++)
				arr[i] = nextInt();
			return arr;
		}

		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 {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++) {
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
				if (sb.length() == 18) {
					res += Long.parseLong(sb.toString()) / f;
					sb = new StringBuilder("0");
				}
			}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

	public static void shuffle(int[] a) {
		int n = a.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}

}