#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int M = 100005;
int sum[26][4 * M];
int prop[26][4 * M];
void propagate(int id, int l, int r, int k) {
  if (prop[id][k] == -1) return;
  if (l != r) {
    prop[id][k * 2] = prop[id][k];
    prop[id][k * 2 + 1] = prop[id][k];
  }
  sum[id][k] = (r - l + 1) * prop[id][k];
  prop[id][k] = -1;
}
void update(int id, int l, int r, int k, int L, int R, int val) {
  propagate(id, l, r, k);
  if (l > R || r < L) return;
  if (l >= L && r <= R) {
    prop[id][k] = val;
    propagate(id, l, r, k);
    return;
  }
  int mid = (l + r) / 2;
  update(id, l, mid, k * 2, L, R, val);
  update(id, mid + 1, r, k * 2 + 1, L, R, val);
  sum[id][k] = sum[id][k * 2] + sum[id][k * 2 + 1];
}
long long query(int id, int l, int r, int k, int L, int R) {
  propagate(id, l, r, k);
  if (l > R || r < L) return 0;
  if (l >= L && r <= R) return sum[id][k];
  int mid = (l + r) / 2;
  return query(id, l, mid, k * 2, L, R) +
         query(id, mid + 1, r, k * 2 + 1, L, R);
}
string s;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  memset((prop), -1, sizeof(prop));
  int n, m;
  cin >> n >> m;
  cin >> s;
  for (int i = 1; i <= n; i++) {
    int x = s[i - 1] - 'a';
    update(x, 1, n, 1, i, i, 1);
  }
  int frq[26] = {0};
  while (m--) {
    int l, r, typ;
    cin >> l >> r >> typ;
    for (int i = 0; i < 26; i++) {
      frq[i] = query(i, 1, n, 1, l, r);
    }
    if (typ == 1) {
      int cnt = 0;
      for (int i = 0; i < 26; i++) {
        update(i, 1, n, 1, l, r, 0);
        update(i, 1, n, 1, l + cnt, l + cnt + frq[i] - 1, 1);
        cnt += frq[i];
      }
    } else {
      int cnt = 0;
      for (int i = 25; i >= 0; i--) {
        update(i, 1, n, 1, l, r, 0);
        update(i, 1, n, 1, l + cnt, l + cnt + frq[i] - 1, 1);
        cnt += frq[i];
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 26; j++) {
      if (query(j, 1, n, 1, i, i)) {
        cout << (char)('a' + j);
        break;
      }
    }
  }
  cout << endl;
  return 0;
}

### Prompt

Your challenge is to write a cpp solution to the following 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>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int M = 100005;
int sum[26][4 * M];
int prop[26][4 * M];
void propagate(int id, int l, int r, int k) {
  if (prop[id][k] == -1) return;
  if (l != r) {
    prop[id][k * 2] = prop[id][k];
    prop[id][k * 2 + 1] = prop[id][k];
  }
  sum[id][k] = (r - l + 1) * prop[id][k];
  prop[id][k] = -1;
}
void update(int id, int l, int r, int k, int L, int R, int val) {
  propagate(id, l, r, k);
  if (l > R || r < L) return;
  if (l >= L && r <= R) {
    prop[id][k] = val;
    propagate(id, l, r, k);
    return;
  }
  int mid = (l + r) / 2;
  update(id, l, mid, k * 2, L, R, val);
  update(id, mid + 1, r, k * 2 + 1, L, R, val);
  sum[id][k] = sum[id][k * 2] + sum[id][k * 2 + 1];
}
long long query(int id, int l, int r, int k, int L, int R) {
  propagate(id, l, r, k);
  if (l > R || r < L) return 0;
  if (l >= L && r <= R) return sum[id][k];
  int mid = (l + r) / 2;
  return query(id, l, mid, k * 2, L, R) +
         query(id, mid + 1, r, k * 2 + 1, L, R);
}
string s;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  memset((prop), -1, sizeof(prop));
  int n, m;
  cin >> n >> m;
  cin >> s;
  for (int i = 1; i <= n; i++) {
    int x = s[i - 1] - 'a';
    update(x, 1, n, 1, i, i, 1);
  }
  int frq[26] = {0};
  while (m--) {
    int l, r, typ;
    cin >> l >> r >> typ;
    for (int i = 0; i < 26; i++) {
      frq[i] = query(i, 1, n, 1, l, r);
    }
    if (typ == 1) {
      int cnt = 0;
      for (int i = 0; i < 26; i++) {
        update(i, 1, n, 1, l, r, 0);
        update(i, 1, n, 1, l + cnt, l + cnt + frq[i] - 1, 1);
        cnt += frq[i];
      }
    } else {
      int cnt = 0;
      for (int i = 25; i >= 0; i--) {
        update(i, 1, n, 1, l, r, 0);
        update(i, 1, n, 1, l + cnt, l + cnt + frq[i] - 1, 1);
        cnt += frq[i];
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 26; j++) {
      if (query(j, 1, n, 1, i, i)) {
        cout << (char)('a' + j);
        break;
      }
    }
  }
  cout << endl;
  return 0;
}

```