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


import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;

public class Main{
	
	static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[100005]; // line length+1
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
	
	static class FastScanner {

	    private final BufferedReader bufferedReader;
	    private StringTokenizer stringTokenizer;

	    public FastScanner() {
	        bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public String next() {
	        while (stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
	            try {
	                stringTokenizer = new StringTokenizer(bufferedReader.readLine());
	            } catch (IOException e) {
	                throw new RuntimeException("Can't read next value", e);
	            }
	        }
	        return stringTokenizer.nextToken();
	    }

	    public int nextInt() {
	        return Integer.parseInt(next());
	    }

	    public long nextLong() {
	        return Long.parseLong(next());
	    }

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

	    public String nextLine(){
	        String str = "";
	        try {
	            str = bufferedReader.readLine();
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
	        return str;
	    }
	}
	
	static void closeall() throws IOException{
		printWriter.close();
		sc.close();
		in.close();
	}
	static Scanner sc = new Scanner(System.in);
	static Reader in = new Reader();
	static FastScanner fastScanner = new FastScanner();
	static PrintWriter printWriter = new PrintWriter(new BufferedOutputStream(System.out));
	static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
	static long INF = (long)(1e18);
	
	int V,E;
	ArrayList<Integer> adj[];
	Main(){
	}
	Main(int v,int e){
		V=v;
		E=e;
		adj=new ArrayList[v];
		for(int i=0;i<v;i++)
			adj[i] = new ArrayList<>();
	}
	void addEdge(int u,int v){
		adj[u].add(v);
		adj[v].add(u);
	}
	
	static class e implements Comparable<e>{
		long len;
		int pos;
		e(long a,int b){
			len=a;
			pos=b;
		}
		public int compareTo(e item) {
			// TODO Auto-generated method stub
			return Long.compare(this.len, item.len);
		}
	}
	
	static long power(long a,long k)
	{
		long m = 998244353;
	    long ans=1;
	    long tmp=a%m;
	    while(k>0)
	    {
	        if(k%2==1)
	        	ans=ans*tmp%m;
	        tmp=tmp*tmp%m;
	        k>>=1;
	    }
	    return ans;
	}
	
	static class Pair{
		int a,b;
		Pair(int x,int y){
			a = x;
			b = y;
		}
	}
	public static void main(String args[])throws IOException{
		//String str = read.readLine();
		//Scanner sc = new Scanner(str);
		int n = in.nextInt();
		int q = in.nextInt();
		String temp = in.readLine();
		String s = in.readLine();
		int len = 2*(int)Math.pow(2,Math.ceil(Math.log(n)/Math.log(2)))-1;
		Main ob = new Main(len);
		char ch[] = s.toCharArray();
		for(int i=0;i<26;i++)
			ob.constructTree(ch,0,n-1,0,i);
		int[] occurences = new int[26];
		for(int i=0;i<q;i++){
			//str = read.readLine();
			//sc = new Scanner(str);
			int qlow = in.nextInt()-1;
			int qhigh = in.nextInt()-1;
			int p = in.nextInt();
			Arrays.fill(occurences, 0);
			for(int j=0;j<26;j++)
				occurences[j] = ob.query(qlow,qhigh,0,n-1,0,j);
			int start = qlow;
			int end = qlow-1;
			int k = 0;
			if(p==1){
				while(k<26){
					while(occurences[k]==0){
						k++;
						if(k>=26)
							break;
					}
					if(k>=26)
						break;
					start = end+1;
					end = start+occurences[k]-1;
					ob.updatelazy(start,end,0,n-1,0,k,1);
					if(qlow<=start-1)
						ob.updatelazy(qlow,start-1,0,n-1,0,k,-1);
					if(end+1<=qhigh)
						ob.updatelazy(end+1,qhigh,0,n-1,0,k,-1);
					occurences[k] = 0;
				}
			}
			else{
				k=25;
				while(k>=0){
					while(occurences[k]==0){
						k--;
						if(k<0)
							break;
					}
					if(k<0)
						break;
					start = end+1;
					end = start+occurences[k]-1;
					ob.updatelazy(start,end,0,n-1,0,k,1);
					if(qlow<=start-1)
						ob.updatelazy(qlow,start-1,0,n-1,0,k,-1);
					if(end+1<=qhigh)
						ob.updatelazy(end+1,qhigh,0,n-1,0,k,-1);
					occurences[k] = 0;
				}
			}
		}
		for(int i=0;i<n;i++){
			int k = 0;
			while(ob.query(i, i, 0, n-1, 0, k)!=1 )
				k++;
			printWriter.print((char)(k+97));
		}
		closeall();
	}
	int tree[][];
	int lazy[][];
	int size;
	Main(int len){
		size = len;
		tree = new int[26][len];
		lazy = new int[26][len];
		for(int i=0;i<26;i++)
			Arrays.fill(lazy[i],-1);
	}
	
	void constructTree(char[] ch, int low, int high, int pos, int c){
		if(low==high){
			if(ch[low]==c+97)
				tree[c][pos]=1;
			else
				tree[c][pos]=0;
			return;
		}
		int mid = (low+high)/2;
		constructTree(ch,low,mid,2*pos+1,c);
		constructTree(ch,mid+1,high,2*pos+2,c);
		tree[c][pos] = tree[c][2*pos+1]+tree[c][2*pos+2];
	}
	
	void updatelazy(int start, int end, int low, int high, int pos, int c, int delta){
		if(delta==1){
			if(low>high)
				return;
			if(lazy[c][pos]!=-1){
				tree[c][pos]=lazy[c][pos];
				if(low!=high){
					lazy[c][2*pos+1]=(lazy[c][pos]+1)/2;
					lazy[c][2*pos+2]=(lazy[c][pos])/2;
				}
				lazy[c][pos]=-1;
			}
			if(start>high || end<low)
				return;
			if(start<=low && high<=end){
				tree[c][pos]=high-low+1;
				if(low!=high){
					int mid = (low+high)/2;
					lazy[c][2*pos+1]=mid-low+1;
					lazy[c][2*pos+2]=high-mid;
				}
				return;
			}
			int mid = (low+high)/2;
			updatelazy(start,end,low,mid,2*pos+1,c,delta);
			updatelazy(start,end,mid+1,high,2*pos+2,c,delta);
			tree[c][pos] = tree[c][2*pos+1]+tree[c][2*pos+2];
		}
		else{
			if(low>high)
				return;
			if(lazy[c][pos]!=-1){
				tree[c][pos]=lazy[c][pos];
				if(low!=high){
					lazy[c][2*pos+1]=(lazy[c][pos]+1)/2;
					lazy[c][2*pos+2]=(lazy[c][pos])/2;
				}
				lazy[c][pos]=-1;
			}
			if(start>high || end<low)
				return;
			if(start<=low && high<=end){
				tree[c][pos]=0;
				if(low!=high){
					int mid = (low+high)/2;
					lazy[c][2*pos+1]=0;
					lazy[c][2*pos+2]=0;
				}
				return;
			}
			int mid = (low+high)/2;
			updatelazy(start,end,low,mid,2*pos+1,c,delta);
			updatelazy(start,end,mid+1,high,2*pos+2,c,delta);
			tree[c][pos] = tree[c][2*pos+1]+tree[c][2*pos+2];
		}
	}
	
	int query(int qlow, int qhigh, int low, int high, int pos, int c){
		if(lazy[c][pos]!=-1){
			tree[c][pos]=lazy[c][pos];
			if(low!=high){
				lazy[c][2*pos+1]=(lazy[c][pos]+1)/2;
				lazy[c][2*pos+2]=(lazy[c][pos])/2;
			}
			lazy[c][pos]=-1;
		}
		if(qlow<=low && qhigh>=high)
			return tree[c][pos];
		if(qlow>high || qhigh<low)
			return 0;
		int mid = (low+high)/2;
		return query(qlow,qhigh,low,mid,2*pos+1,c)+query(qlow,qhigh,mid+1,high,2*pos+2,c);
	}
}