#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 5;
const int inf = 0x3f3f3f3f;
int n, q;
char s[maxn], C;
struct SegTree {
  int sum[maxn << 2];
  int lazy[maxn << 2];
  void pushDown(int rt, int L) {
    if (~lazy[rt]) {
      int l = rt << 1, r = rt << 1 | 1;
      sum[l] = lazy[rt] * (L - (L >> 1));
      sum[r] = lazy[rt] * (L >> 1);
      lazy[l] = lazy[r] = lazy[rt];
      lazy[rt] = -1;
    }
  }
  void build(int l, int r, int rt) {
    lazy[rt] = -1;
    if (l == r)
      sum[rt] = (s[l] == C);
    else {
      int m = (l + r) >> 1;
      build(l, m, rt << 1);
      build(m + 1, r, rt << 1 | 1);
      sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }
  }
  void update(int L, int R, int v, int l, int r, int rt) {
    if (L <= l && R >= r) {
      sum[rt] = v * (r - l + 1);
      lazy[rt] = v;
      return;
    }
    pushDown(rt, r - l + 1);
    int m = (l + r) >> 1;
    if (L <= m) update(L, R, v, l, m, rt << 1);
    if (R > m) update(L, R, v, m + 1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  }
  int query(int L, int R, int l, int r, int rt) {
    if (L <= l && R >= r) return sum[rt];
    pushDown(rt, r - l + 1);
    int m = (l + r) >> 1, ret = 0;
    if (L <= m) ret += query(L, R, l, m, rt << 1);
    if (R > m) ret += query(L, R, m + 1, r, rt << 1 | 1);
    return ret;
  }
} T[26];
int main() {
  scanf("%d%d%s", &n, &q, s + 1);
  for (int i = 0; i < 26; i++) {
    C = i + 'a';
    T[i].build(1, n, 1);
  }
  int L, R, O, cnt[26];
  while (q--) {
    scanf("%d%d%d", &L, &R, &O);
    for (int i = 0; i < 26; i++) {
      cnt[i] = T[i].query(L, R, 1, n, 1);
      if (cnt[i]) T[i].update(L, R, 0, 1, n, 1);
    }
    if (O == 1) {
      for (int i = 0; i < 26; i++)
        if (cnt[i]) {
          T[i].update(L, L + cnt[i] - 1, 1, 1, n, 1);
          L += cnt[i];
        }
    } else {
      for (int i = 0; i < 26; i++)
        if (cnt[i]) {
          T[i].update(R - cnt[i] + 1, R, 1, 1, n, 1);
          R -= cnt[i];
        }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 26; j++) {
      if (T[j].query(i, i, 1, n, 1)) {
        putchar(j + 'a');
        break;
      }
    }
  }
  putchar('\n');
  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;
const int maxn = 100000 + 5;
const int inf = 0x3f3f3f3f;
int n, q;
char s[maxn], C;
struct SegTree {
  int sum[maxn << 2];
  int lazy[maxn << 2];
  void pushDown(int rt, int L) {
    if (~lazy[rt]) {
      int l = rt << 1, r = rt << 1 | 1;
      sum[l] = lazy[rt] * (L - (L >> 1));
      sum[r] = lazy[rt] * (L >> 1);
      lazy[l] = lazy[r] = lazy[rt];
      lazy[rt] = -1;
    }
  }
  void build(int l, int r, int rt) {
    lazy[rt] = -1;
    if (l == r)
      sum[rt] = (s[l] == C);
    else {
      int m = (l + r) >> 1;
      build(l, m, rt << 1);
      build(m + 1, r, rt << 1 | 1);
      sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }
  }
  void update(int L, int R, int v, int l, int r, int rt) {
    if (L <= l && R >= r) {
      sum[rt] = v * (r - l + 1);
      lazy[rt] = v;
      return;
    }
    pushDown(rt, r - l + 1);
    int m = (l + r) >> 1;
    if (L <= m) update(L, R, v, l, m, rt << 1);
    if (R > m) update(L, R, v, m + 1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  }
  int query(int L, int R, int l, int r, int rt) {
    if (L <= l && R >= r) return sum[rt];
    pushDown(rt, r - l + 1);
    int m = (l + r) >> 1, ret = 0;
    if (L <= m) ret += query(L, R, l, m, rt << 1);
    if (R > m) ret += query(L, R, m + 1, r, rt << 1 | 1);
    return ret;
  }
} T[26];
int main() {
  scanf("%d%d%s", &n, &q, s + 1);
  for (int i = 0; i < 26; i++) {
    C = i + 'a';
    T[i].build(1, n, 1);
  }
  int L, R, O, cnt[26];
  while (q--) {
    scanf("%d%d%d", &L, &R, &O);
    for (int i = 0; i < 26; i++) {
      cnt[i] = T[i].query(L, R, 1, n, 1);
      if (cnt[i]) T[i].update(L, R, 0, 1, n, 1);
    }
    if (O == 1) {
      for (int i = 0; i < 26; i++)
        if (cnt[i]) {
          T[i].update(L, L + cnt[i] - 1, 1, 1, n, 1);
          L += cnt[i];
        }
    } else {
      for (int i = 0; i < 26; i++)
        if (cnt[i]) {
          T[i].update(R - cnt[i] + 1, R, 1, 1, n, 1);
          R -= cnt[i];
        }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 26; j++) {
      if (T[j].query(i, i, 1, n, 1)) {
        putchar(j + 'a');
        break;
      }
    }
  }
  putchar('\n');
  return 0;
}

```