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;
const int N = 1e5;
int n, q;
int st[26][4 * N], lz[26][4 * N];
string s;
void prop(int c, int idx, int l, int r) {
  if (lz[c][idx] == -1) return;
  st[c][idx] = (r - l + 1) * lz[c][idx];
  if (l < r) {
    lz[c][2 * idx] = lz[c][idx];
    lz[c][2 * idx + 1] = lz[c][idx];
  }
  lz[c][idx] = -1;
}
void update(int c, int idx, int l, int r, int x, int y, int val) {
  prop(c, idx, l, r);
  if (l > y || r < x) return;
  if (l >= x && r <= y) {
    lz[c][idx] = val;
    prop(c, idx, l, r);
    return;
  }
  int m = (l + r) / 2;
  if (l <= m) update(c, 2 * idx, l, m, x, y, val);
  if (m + 1 <= r) update(c, 2 * idx + 1, m + 1, r, x, y, val);
  st[c][idx] = st[c][2 * idx] + st[c][2 * idx + 1];
}
int valOf(int c, int idx, int l, int r, int x, int y) {
  prop(c, idx, l, r);
  if (l > y || r < x) return 0;
  if (l >= x && r <= y) return st[c][idx];
  int m = (l + r) / 2;
  return valOf(c, 2 * idx, l, m, x, y) + valOf(c, 2 * idx + 1, m + 1, r, x, y);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q >> s;
  for (int i = 0; i < 26; i++) {
    for (int j = 0; j < 4 * N; j++) {
      lz[i][j] = -1;
    }
  }
  for (int i = 1; i <= n; i++) {
    int c = s[i - 1] - 'a';
    update(c, 1, 1, n, i, i, 1);
  }
  while (q--) {
    int l, r, k;
    cin >> l >> r >> k;
    vector<int> cnt(26);
    for (int i = 0; i < 26; i++) {
      cnt[i] = valOf(i, 1, 1, n, l, r);
    }
    if (k == 1) {
      for (int i = 0, j = l; i < 26; i++) {
        if (cnt[i] == 0) continue;
        int fr = j - l, bc = r - l + 1 - fr - cnt[i];
        if (fr > 0) update(i, 1, 1, n, l, l + fr - 1, 0);
        update(i, 1, 1, n, j, j + cnt[i] - 1, 1);
        j += cnt[i];
        if (bc > 0) update(i, 1, 1, n, j, j + bc - 1, 0);
      }
    } else {
      for (int i = 25, j = l; i >= 0; i--) {
        if (cnt[i] == 0) continue;
        int fr = j - l, bc = r - l + 1 - fr - cnt[i];
        if (fr > 0) update(i, 1, 1, n, l, l + fr - 1, 0);
        update(i, 1, 1, n, j, j + cnt[i] - 1, 1);
        j += cnt[i];
        if (bc > 0) update(i, 1, 1, n, j, j + bc - 1, 0);
      }
    }
  }
  string res;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 26; j++) {
      char c = j + 'a';
      if (valOf(j, 1, 1, n, i, i) != 0) {
        res += c;
        break;
      }
    }
  }
  cout << res << '\n';
  return 0;
}