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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int n, q, cnt[26], tcnt[26], l, r, k;
char ans[100005];
set<pair<int, int> > st[26];
void print(bool fl) {
  for (int i = 0; i < (int)26; i++) {
    int a = 0;
    for (set<pair<int, int> >::iterator it = st[i].begin(); it != st[i].end();
         it++)
      for (int j = it->first; j < (int)it->second + 1; j++)
        ans[j - 1] = 'a' + i, a++;
  }
  ans[n] = '\0';
  if (fl) printf("%s\n", ans);
}
int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", ans);
  for (int i = 0; i < (int)n; i++) {
    st[(int)ans[i] - 'a'].insert(make_pair(i + 1, i + 1));
  }
  while (q--) {
    int pos = 0;
    scanf("%d%d", &l, &r);
    scanf("%d", &k);
    for (int i = 0; i < (int)26; i++) {
      set<pair<int, int> >::iterator it =
                                         st[i].upper_bound(make_pair(l, n + 1)),
                                     tmp;
      int sz = 0;
      if (it != st[i].begin()) {
        it--;
        if (it->second >= l) {
          if (it->first < l) st[i].insert(make_pair(it->first, l - 1));
          if (it->second > r)
            st[i].insert(make_pair(r + 1, it->second)), sz += (r - l + 1);
          else
            sz += (it->second - l + 1);
          st[i].erase(it);
        }
        it = st[i].upper_bound(make_pair(l, n + 1));
      }
      while (it != st[i].end() && it->first <= r) {
        if (it->second > r) {
          st[i].insert(make_pair(r + 1, it->second)), sz += (r - it->first + 1);
        } else
          sz += (it->second - it->first + 1);
        tmp = it;
        it++;
        st[i].erase(tmp);
      }
      if (!sz) continue;
      if (k)
        st[i].insert(make_pair(l + pos, l + pos + sz - 1));
      else
        st[i].insert(make_pair(r - pos - sz + 1, r - pos));
      pos += sz;
    }
  }
  print(true);
  return 0;
}