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.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Arrays;

public class E558 {
	
	/*
	
	class Node {
		int l, r;
		int value;
		
		boolean on, off;
		
		Node left, right;
		
		Node(int ll, int rr, int[] a) {
			l = ll; r = rr;
			if(l == r) {
				value = a[l];
				return;
			}
			int mid = ll + rr >> 1;
			left = new Node(ll, mid, a);
			right = new Node(mid + 1, rr, a);
			value = left.get() + right.get();
		}
		
		int get() {
			if(off) return 0;
			if(on) return r - l + 1;
			return value;
		}
		
		void propOff() {
			if(!off) return;
			off = false;
			value = 0;
			if(left != null) {
				left.off = true;
				left.on = false;
			}
			if(right != null) {
				right.off = true;
				right.on = false;
			}
		}
		
		void propOn() {
			if(!on) return;
			on = false;
			value = r - l + 1;
			if(left != null) {
				left.on = true;
				left.off = false;
			}
			if(right != null) {
				right.on = true;
				right.off = false;
			}
		}
		
		void turnOff(int ll, int rr) {
			if(r < ll || l > rr) return;
			if(ll <= l && r <= rr) {
				off = true;
				on = false;
				return;
			}
			propOff();
			left.turnOff(ll, rr);
			right.turnOff(ll, rr);
			value = left.get() + right.get();
		}
		
		void turnOn(int ll, int rr) {
			if(r < ll || l > rr) return;
			if(ll <= l && r <= rr) {
				on = true;
				off = false;
				return;
			}
			propOn();
			left.turnOff(ll, rr);
			right.turnOff(ll, rr);
			value = left.get() + right.get();
		}
		
		int count(int ll, int rr) {
			if(r < ll || l > rr) return 0;
			if(ll <= l && r <= rr) return get();
			propOn(); propOff();
			return left.count(ll, rr) + right.count(ll, rr);
		}
		
		void check() {
			if(on && off) throw new RuntimeException();
			if(left != null) left.check();
			if(right != null) right.check();
		}
	}
	
	*/
	
	final int ON = 1, OFF = -1;
	
	class Node {
		int l, r;
		Node left, right;
		
		int count;
		int lazy;
		
		Node(int ll, int rr, int[] a) {
			l = ll; r = rr;
			if(l == r) {
				count = a[l];
				return;
			}
			int mid = l + r >> 1;
			left = new Node(ll, mid, a);
			right = new Node(mid + 1, rr, a);
			count = left.count + right.count;
		}
		
		int get() {
			if(lazy == OFF) return 0;
			if(lazy == ON) return r - l + 1;
			return count;
		}
		
		void prop() {
			if(lazy == 0) return;
			if(lazy == ON) {
				count = r - l + 1;
				lazy = 0;
				left.lazy = right.lazy = ON;
			} else {
				count = 0;
				lazy = 0;
				left.lazy = right.lazy = OFF;
			}
		}
		
		int count(int ll, int rr) {
			if(ll > r || rr < l) return 0;
			if(ll <= l && r <= rr) return get();
			prop();
			return left.count(ll, rr) + right.count(ll, rr);
		}
		
		void turnOn(int ll, int rr) {
			if(ll > r || rr < l) return;
			if(ll <= l && r <= rr) {
				lazy = ON;
				return;
			}
			prop();
			left.turnOn(ll, rr);
			right.turnOn(ll, rr);
			count = left.get() + right.get();
		}
		
		void turnOff(int ll, int rr) {
			if(ll > r || rr < l) return;
			if(ll <= l && r <= rr) {
				lazy = OFF;
				return;
			}
			prop();
			left.turnOff(ll, rr);
			right.turnOff(ll, rr);
			count = left.get() + right.get();
		}
	}
	
	public void solve(JS in, PrintWriter out) {
		int n = in.nextInt();
		int q = in.nextInt();
		char[] s = in.next().toCharArray();
		Node[] st = new Node[26];
		int[][] a = new int[26][n];
		for(int i = 0; i < n; ++i) a[s[i] - 'a'][i] = 1;
		for(int i = 0; i < 26; ++i) st[i] = new Node(0, n - 1, a[i]);
		while(q-->0) {
			int l = in.nextInt() - 1;
			int r = in.nextInt() - 1;
			int k = in.nextInt();
			if(k == 1) { //non-decreasing (increasing)
				int idx = l;
				for(int c = 0; c < 26; ++c) {
					int count = st[c].count(l, r);
					st[c].turnOff(l, r);
					st[c].turnOn(idx, idx + count - 1);
					idx += count;
				}
			} else { //non-increasing (decreasing)
				int idx = l;
				for(int c = 25; c >= 0; --c) {
					int count = st[c].count(l, r);
					st[c].turnOff(l, r);
					st[c].turnOn(idx, idx + count - 1);
					idx += count;
				}
			}
		}
		
		for(int c = 0; c < 26; ++c) {
			for(int i = 0; i < n; ++i) {
				if(st[c].count(i, i) == 1) {
					s[i] = (char) ('a' + c);
				}
			}
		}
		
		out.println(s);
	}
	
	public static void main(String[] args) {
		JS in = new JS();
		PrintWriter out = new PrintWriter(System.out);
		new E558().solve(in, out);
		out.close();
	}
	
	static class JS{
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;
		
		public JS() {
			in = new BufferedInputStream(System.in, BS);
		}
		
		public JS(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}
		
		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}				
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}
		
		public int nextInt() {
			return (int)nextLong();
		}
		
		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}
		
		public double nextDouble() {
		    while(c!='.'&&c!='-'&&(c <'0' || c>'9')) c = nextChar();
		    boolean neg = c=='-';
		    if(neg)c=nextChar();
		    boolean fl = c=='.';
		    double cur = nextLong();
		    if(fl) return neg ? -cur/num : cur/num;
		    if(c == '.') {
			double next = nextLong();
			return neg ? -cur-next/num : cur+next/num;
		    }
		    else return neg ? -cur : cur;
		}
		
		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}
		
		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
	}
}