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>
const double EPS = 1e-24;
const long long int MOD = 1000000007ll;
const double PI = 3.14159265359;
int INF = 2147483645;
long long int INFINF = 9223372036854775807;
template <class T>
T Max2(T a, T b) {
  return a < b ? b : a;
}
template <class T>
T Min2(T a, T b) {
  return a < b ? a : b;
}
template <class T>
T Max3(T a, T b, T c) {
  return Max2(Max2(a, b), c);
}
template <class T>
T Min3(T a, T b, T c) {
  return Min2(Min2(a, b), c);
}
template <class T>
T Max4(T a, T b, T c, T d) {
  return Max2(Max2(a, b), Max2(c, d));
}
template <class T>
T Min4(T a, T b, T c, T d) {
  return Min2(Min2(a, b), Max2(c, d));
}
using namespace std;
int n, q;
string s;
int blocksz;
int blocks[1000][26];
int lazy[1000];
void update(int b) {
  if (lazy[b] == 0) return;
  int l = b * blocksz;
  if (lazy[b] == 1) {
    for (int i = 0; i < 26; i++)
      for (int j = 0; j < blocks[b][i]; j++) s[l++] = (char)(i + 'a');
  } else {
    for (int i = 25; i >= 0; i--)
      for (int j = 0; j < blocks[b][i]; j++) s[l++] = (char)(i + 'a');
  }
  lazy[b] = 0;
}
void ppp() {
  for (int i = 0; i <= n / blocksz; i++) {
    for (int j = 0; j < 26; j++) cout << blocks[i][j] << " ";
    cout << "\n";
  }
  cout << "\n";
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> q;
  cin >> s;
  blocksz = ceil(sqrt(n));
  for (int i = 0; i < n; i++) blocks[i / blocksz][s[i] - 'a']++;
  while (q--) {
    int l, r, k;
    cin >> l >> r >> k;
    l--, r--;
    int c_l = l / blocksz;
    int c_r = r / blocksz;
    if (c_l == c_r) {
      update(c_l);
      if (k == 1) {
        vector<char> v;
        for (int i = l; i <= r; i++) v.push_back(s[i]);
        sort(v.begin(), v.end());
        for (int i = 0; i < v.size(); i++) s[l + i] = v[i];
      } else {
        vector<char> v;
        for (int i = l; i <= r; i++) v.push_back(s[i]);
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
        for (int i = 0; i < v.size(); i++) s[l + i] = v[i];
      }
    } else {
      update(c_l);
      update(c_r);
      int cnt[26];
      int start;
      for (int i = 0; i < 26; i++) cnt[i] = 0;
      for (int i = l; i <= (c_l + 1) * blocksz - 1; i++) cnt[s[i] - 'a']++;
      for (int i = c_r * blocksz; i <= r; i++) cnt[s[i] - 'a']++;
      for (int i = c_l + 1; i <= c_r - 1; i++)
        for (int j = 0; j < 26; j++) cnt[j] += blocks[i][j];
      for (int i = l; i <= (c_l + 1) * blocksz - 1; i++)
        blocks[c_l][s[i] - 'a']--;
      for (int i = c_r * blocksz; i <= r; i++) blocks[c_r][s[i] - 'a']--;
      for (int i = c_l + 1; i <= c_r - 1; i++)
        for (int j = 0; j < 26; j++) blocks[i][j] = 0;
      if (k == 1) {
        for (int i = c_l + 1; i <= c_r - 1; i++) lazy[i] = 1;
        start = l;
        for (int j = 0; j < 26; j++) {
          while (cnt[j]) {
            if (start == (c_l + 1) * blocksz) goto label1;
            s[start++] = (char)(j + 'a');
            blocks[c_l][j]++;
            cnt[j]--;
          }
        }
      label1:
        for (int i = c_l + 1; i <= c_r - 1; i++) {
          int need = blocksz;
          for (int j = 0; j < 26; j++) {
            if (cnt[j] <= need) {
              blocks[i][j] += cnt[j];
              need -= cnt[j];
              cnt[j] = 0;
            } else {
              blocks[i][j] += need;
              cnt[j] -= need;
              need = 0;
            }
          }
        }
        start = (c_r)*blocksz;
        for (int j = 0; j < 26; j++) {
          while (cnt[j]) {
            s[start++] = (char)(j + 'a');
            blocks[c_r][j]++;
            cnt[j]--;
          }
        }
      } else {
        for (int i = c_l + 1; i <= c_r - 1; i++) lazy[i] = 2;
        start = l;
        for (int j = 25; j >= 0; j--) {
          while (cnt[j]) {
            if (start == (c_l + 1) * blocksz) goto label2;
            s[start++] = (char)(j + 'a');
            blocks[c_l][j]++;
            cnt[j]--;
          }
        }
      label2:
        for (int i = c_l + 1; i <= c_r - 1; i++) {
          int need = blocksz;
          for (int j = 25; j >= 0; j--) {
            if (cnt[j] <= need) {
              blocks[i][j] += cnt[j];
              need -= cnt[j];
              cnt[j] = 0;
            } else {
              blocks[i][j] += need;
              cnt[j] -= need;
              need = 0;
            }
          }
        }
        start = (c_r)*blocksz;
        for (int j = 25; j >= 0; j--) {
          while (cnt[j]) {
            s[start++] = (char)(j + 'a');
            blocks[c_r][j]++;
            cnt[j]--;
          }
        }
      }
    }
  }
  for (int i = 0; i <= n / blocksz; i++) update(i);
  cout << s;
  return 0;
}