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

public class Main
{
	static long mod=1000000007;
	public static void main(String[] args) throws IOException
	{
		Scanner in=new Scanner(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		int n=in.nextInt(),m=in.nextInt();
		char[] s=in.next().toCharArray();
		TreeMap<Integer,Character> tm=new TreeMap<>();
		for(int i=0;i<n;i++)
			tm.put(i+1,s[i]);
		tm.put(n+1,'*');
		while(m-->0)
		{
			int l=in.nextInt();
			int r=in.nextInt();
			Map.Entry<Integer,Character> e1=tm.floorEntry(l);
			if(e1.getKey()<l)
				tm.put(l,e1.getValue());
			Map.Entry<Integer,Character> e2=tm.floorEntry(r+1);
			if(e2.getKey()<r+1)
				tm.put(r+1,e2.getValue());
			SortedMap<Integer,Character> tail=tm.tailMap(l);
			int[] c=new int[26];
			e1=tm.floorEntry(l);
			ArrayList<Integer> al=new ArrayList<>();
			for(Map.Entry<Integer,Character> e:tail.entrySet())
			{
				if(e1.getKey()>r)
					break;
				c[e1.getValue()-'a']+=e.getKey()-e1.getKey();
				al.add(e.getKey());
				e1=e;
				//System.out.println(e.getValue()+" "+e.getKey());
			}
			for(int i=0;i<al.size()-1;i++)
			{
				tm.remove(al.get(i));
			}
			if(in.nextInt()==1)
			{
				for(int i=0;i<26;l+=c[i++])
				{
					if(c[i]>0)
						tm.put(l,(char)('a'+i));
				}
			}
			else
			{
				for(int i=25;i>=0;l+=c[i--])
				{
					if(c[i]>0)
						tm.put(l,(char)('a'+i));
				}
			}
		}
		Map.Entry<Integer,Character> e1=tm.firstEntry();
		for(Map.Entry<Integer,Character> e2:tm.entrySet())
		{
			for(int i=0;i<e2.getKey()-e1.getKey();i++)
				pw.print(e1.getValue());
			e1=e2;
		}
		for(int i=0;i<n-e1.getKey()+1;i++)
			pw.print(e1.getValue());
		pw.flush();
	}
}

class FastReader
{
	BufferedReader br;
	StringTokenizer st;
 
	public FastReader()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}
 
	public String next() throws IOException
	{
		if(st==null || !st.hasMoreElements())
		{
			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());
	}
}