CF558E A Simple Task

5 seconds per test
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, ).

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:

题意：给你一串字符串，每次操作对一段区间内的字符串作升序或降序排序。输出所有操作后的字符串。

　 >错误思路：把a_{z依次赋以1}26的值，然后做区间的修改。。。写到一半就暴毙了

思路：
  这是直接听归神例会讲的方法。为a~z各建立一棵线段树，然后把字符放入它自己的线段树中。每次区间排序的时候，区间求该字符的个数，区间清空，然后接着之前的顺序赋值。
  比如ababa，变为升序时，t=1，1_{（1+3-1）变为a，然后t变为4，4}（4+2-1）变为b.
  复杂度O（m*26logn）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;

int tree[30][4*maxn],lazy[30][4*maxn];
int n,m;
char c;
//lazy -1 未使用, 0或1 区间赋值为0或1
void pushup(int trnum,int now)
{
    tree[trnum][now]=tree[trnum][now<<1]+tree[trnum][now<<1|1];
}

void pushdown(int trnum,int num,int l,int mid,int r)
{
    if(lazy[trnum][num]==0)
    {
        tree[trnum][num<<1]=tree[trnum][num<<1|1]=lazy[trnum][num<<1]=lazy[trnum][num<<1|1]=0;
        lazy[trnum][num]=-1;
    }
    else if(lazy[trnum][num]==1)
    {
        tree[trnum][num<<1]=mid-l+1;
        tree[trnum][num<<1|1]=r-mid;
        lazy[trnum][num<<1]=lazy[trnum][num<<1|1]=1;
        lazy[trnum][num]=-1;
    }
}

void addline(int trnum,int num,int le,int ri,int l,int r)
{
    if(l>=le&&r<=ri)
    {
        tree[trnum][num]=r-l+1;
        lazy[trnum][num]=1;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(trnum,num,l,mid,r);
    if(mid>=le) addline(trnum,num<<1,le,ri,l,mid);
    if(mid<ri) addline(trnum,num<<1|1,le,ri,mid+1,r);
    pushup(trnum,num);
}

void add(int num,int pos,int trnum,int l,int r)
{
    if(l==r)
    {
        tree[trnum][num]=1;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) add(num<<1,pos,trnum,l,mid);
    else add(num<<1|1,pos,trnum,mid+1,r);
    pushup(trnum,num);
}//其实add可以和addline合并但是当时没想到这么多就先写了个单点的

int counts(int trnum,int num,int le,int ri,int l,int r)
{
    if(l>=le&&r<=ri)
    {
        lazy[trnum][num]=0;
        int t=tree[trnum][num];
        tree[trnum][num]=0;
        return t;
    }
    int mid=(l+r)>>1,sum=0;
    pushdown(trnum,num,l,mid,r);
    if(mid>=le) sum+=counts(trnum,num<<1,le,ri,l,mid);
    if(mid<ri) sum+=counts(trnum,num<<1|1,le,ri,mid+1,r);
    pushup(trnum,num);
    return sum;
}

void run()
{
    cin>>n>>m;
    c=getchar();
    for(int i=1;i<=n;i++)
    {
        c=getchar();
        add(1,i,c-'a',1,n);
    }
    while(m--)
    {
        int le,ri,t,xu,totnum;
        scanf("%d%d%d",&le,&ri,&xu);
        
        if(xu)
        {
            t=le;
            for(int i=0;i<26;i++)
            {
                totnum=counts(i,1,le,ri,1,n);
                //cout<<i<<' '<<totnum<<endl;
                if(totnum)
                {
                    addline(i,1,t,t+totnum-1,1,n);
                    t+=totnum;
                }
            }
        }
        else
        {
            t=ri;
            for(int i=0;i<26;i++)
            {
                totnum=counts(i,1,le,ri,1,n);
                //cout<<i<<' '<<totnum<<endl;
                if(totnum)
                {
                    addline(i,1,t-totnum+1,t,1,n);
                    t-=totnum;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<26;j++)
        {
            if(counts(j,1,i,i,1,n))
            {
                printf("%c",'a'+j);
                break;
            }
            //cout<<i<<' '<<j<<endl;
        }
    }
}

void init()
{
    memset(lazy,-1,sizeof(lazy));
} 

int main()
{
    if(fopen("test.txt","r")!=NULL)
        freopen("test.txt","r",stdin);
    init();
    run();
    return 0;
}