#include <bits/stdc++.h>
using namespace std;
inline int in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline string get() {
  char ch[1000010];
  scanf("%s", ch);
  return ch;
}
const int MAX_LG = 21;
const int maxn = 1e5 + 10;
const int base = 29;
const int mod = 1e9 + 7;
const int INF = 1e9 + 100;
int n, m;
string s;
int segtree[4 * maxn][26];
int cnt[26];
int lazy[4 * maxn];
inline void build(int p, int l, int r) {
  if (l == r) {
    segtree[p][s[l] - 'a'] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(2 * p + 1, l, mid);
  build(2 * p + 2, mid + 1, r);
  for (int i = 0; i < 26; i++)
    segtree[p][i] = segtree[2 * p + 1][i] + segtree[2 * p + 2][i];
}
inline void push(int p, int l, int r) {
  if (lazy[p] == -1) return;
  lazy[2 * p + 1] = lazy[2 * p + 2] = lazy[p];
  int mid = (l + r) >> 1;
  for (int i = 0; i < 26; i++) {
    segtree[2 * p + 1][i] = (i == lazy[p] ? mid - l + 1 : 0);
    segtree[2 * p + 2][i] = (i == lazy[p] ? r - mid : 0);
  }
  lazy[p] = -1;
}
inline void doJob(int p, int l, int r, int ql, int qr) {
  if (l > qr || r < ql) return;
  if (l >= ql && r <= qr) {
    for (int i = 0; i < 26; i++) cnt[i] += segtree[p][i];
    return;
  }
  push(p, l, r);
  int mid = (l + r) >> 1;
  doJob(2 * p + 1, l, mid, ql, qr);
  doJob(2 * p + 2, mid + 1, r, ql, qr);
}
inline void update(int p, int l, int r, int ql, int qr, int what) {
  if (l > qr || r < ql) return;
  if (l >= ql && r <= qr) {
    lazy[p] = what;
    for (int i = 0; i < 26; i++) segtree[p][i] = (i == what ? r - l + 1 : 0);
    return;
  }
  push(p, l, r);
  int mid = (l + r) >> 1;
  update(2 * p + 1, l, mid, ql, qr, what);
  update(2 * p + 2, mid + 1, r, ql, qr, what);
  for (int i = 0; i < 26; i++)
    segtree[p][i] = segtree[2 * p + 1][i] + segtree[2 * p + 2][i];
}
inline void dfs(int p, int l, int r) {
  if (l == r) {
    for (int i = 0; i < 26; i++)
      if (segtree[p][i]) s[l] = char(i + 'a');
    return;
  }
  int mid = (l + r) >> 1;
  push(p, l, r);
  dfs(2 * p + 1, l, mid);
  dfs(2 * p + 2, mid + 1, r);
}
int32_t main() {
  n = in(), m = in();
  s = get();
  build(0, 0, n - 1);
  for (int i = 0; i < 4 * maxn; i++) lazy[i] = -1;
  while (m--) {
    int l = in() - 1, r = in() - 1, k = in();
    for (int i = 0; i < 26; i++) cnt[i] = 0;
    doJob(0, 0, n - 1, l, r);
    int cur = l;
    int now = (k == 1 ? 0 : 25);
    while (now >= 0 && now <= 25) {
      if (cnt[now]) update(0, 0, n - 1, cur, cur + cnt[now] - 1, now);
      cur += cnt[now];
      now += (k == 1 ? 1 : -1);
    }
  }
  dfs(0, 0, n - 1);
  cout << s << "\n";
}

### Prompt

Please formulate 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;
inline int in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline string get() {
  char ch[1000010];
  scanf("%s", ch);
  return ch;
}
const int MAX_LG = 21;
const int maxn = 1e5 + 10;
const int base = 29;
const int mod = 1e9 + 7;
const int INF = 1e9 + 100;
int n, m;
string s;
int segtree[4 * maxn][26];
int cnt[26];
int lazy[4 * maxn];
inline void build(int p, int l, int r) {
  if (l == r) {
    segtree[p][s[l] - 'a'] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(2 * p + 1, l, mid);
  build(2 * p + 2, mid + 1, r);
  for (int i = 0; i < 26; i++)
    segtree[p][i] = segtree[2 * p + 1][i] + segtree[2 * p + 2][i];
}
inline void push(int p, int l, int r) {
  if (lazy[p] == -1) return;
  lazy[2 * p + 1] = lazy[2 * p + 2] = lazy[p];
  int mid = (l + r) >> 1;
  for (int i = 0; i < 26; i++) {
    segtree[2 * p + 1][i] = (i == lazy[p] ? mid - l + 1 : 0);
    segtree[2 * p + 2][i] = (i == lazy[p] ? r - mid : 0);
  }
  lazy[p] = -1;
}
inline void doJob(int p, int l, int r, int ql, int qr) {
  if (l > qr || r < ql) return;
  if (l >= ql && r <= qr) {
    for (int i = 0; i < 26; i++) cnt[i] += segtree[p][i];
    return;
  }
  push(p, l, r);
  int mid = (l + r) >> 1;
  doJob(2 * p + 1, l, mid, ql, qr);
  doJob(2 * p + 2, mid + 1, r, ql, qr);
}
inline void update(int p, int l, int r, int ql, int qr, int what) {
  if (l > qr || r < ql) return;
  if (l >= ql && r <= qr) {
    lazy[p] = what;
    for (int i = 0; i < 26; i++) segtree[p][i] = (i == what ? r - l + 1 : 0);
    return;
  }
  push(p, l, r);
  int mid = (l + r) >> 1;
  update(2 * p + 1, l, mid, ql, qr, what);
  update(2 * p + 2, mid + 1, r, ql, qr, what);
  for (int i = 0; i < 26; i++)
    segtree[p][i] = segtree[2 * p + 1][i] + segtree[2 * p + 2][i];
}
inline void dfs(int p, int l, int r) {
  if (l == r) {
    for (int i = 0; i < 26; i++)
      if (segtree[p][i]) s[l] = char(i + 'a');
    return;
  }
  int mid = (l + r) >> 1;
  push(p, l, r);
  dfs(2 * p + 1, l, mid);
  dfs(2 * p + 2, mid + 1, r);
}
int32_t main() {
  n = in(), m = in();
  s = get();
  build(0, 0, n - 1);
  for (int i = 0; i < 4 * maxn; i++) lazy[i] = -1;
  while (m--) {
    int l = in() - 1, r = in() - 1, k = in();
    for (int i = 0; i < 26; i++) cnt[i] = 0;
    doJob(0, 0, n - 1, l, r);
    int cur = l;
    int now = (k == 1 ? 0 : 25);
    while (now >= 0 && now <= 25) {
      if (cnt[now]) update(0, 0, n - 1, cur, cur + cnt[now] - 1, now);
      cur += cnt[now];
      now += (k == 1 ? 1 : -1);
    }
  }
  dfs(0, 0, n - 1);
  cout << s << "\n";
}

```