#include <bits/stdc++.h>
using namespace std;
struct xbk {
  int l, r, s[28], tag;
};
struct Ans {
  int s[28];
} st;
int n, m, a[(100010)];
string s;
inline int read() {
  int w = 0;
  char ch = getchar();
  while (ch > '9' || ch < '0') ch = getchar();
  while (ch >= '0' && ch <= '9') {
    w = (w << 3) + (w << 1) + (ch ^ 48);
    ch = getchar();
  }
  return w;
}
struct STree {
  xbk t[(400010)];
  inline void update(int p) {
    for (int i = 1; i <= 26; i++)
      t[p].s[i] = t[p << 1].s[i] + t[p << 1 | 1].s[i];
    return;
  }
  inline void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) {
      t[p].s[a[l]] = 1;
      return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    update(p);
    return;
  }
  inline void spread(int p) {
    if (!t[p].tag) return;
    for (int i = 1; i <= 26; i++) t[p << 1].s[i] = t[p << 1 | 1].s[i] = 0;
    t[p << 1].s[t[p].tag] = t[p << 1].r - t[p << 1].l + 1;
    t[p << 1 | 1].s[t[p].tag] = t[p << 1 | 1].r - t[p << 1 | 1].l + 1;
    t[p << 1].tag = t[p << 1 | 1].tag = t[p].tag;
    t[p].tag = 0;
  }
  inline void change(int p, int l, int r, int v) {
    if (t[p].l >= l && t[p].r <= r) {
      for (int i = 1; i <= 26; i++) t[p].s[i] = 0;
      t[p].s[v] = (t[p].r - t[p].l + 1), t[p].tag = v;
      return;
    }
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) change(p << 1, l, r, v);
    if (r > mid) change(p << 1 | 1, l, r, v);
    update(p);
    return;
  }
  inline void ask(int p, int l, int r, Ans &res) {
    if (t[p].l >= l && t[p].r <= r) {
      for (int i = 1; i <= 26; i++) res.s[i] += t[p].s[i];
      return;
    }
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) ask(p << 1, l, r, res);
    if (r > mid) ask(p << 1 | 1, l, r, res);
    update(p);
    return;
  }
  inline int askp(int p, int pos) {
    if (t[p].l == t[p].r) {
      for (int i = 1; i <= 26; i++)
        if (t[p].s[i]) return i;
      return 0;
    }
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (pos <= mid) return askp(p << 1, pos);
    if (pos > mid) return askp(p << 1 | 1, pos);
    return 0;
  }
} T;
int main() {
  n = read(), m = read();
  cin >> s;
  for (int i = 0; i < n; i++) a[i + 1] = s[i] - 'a' + 1;
  for (int i = 1; i <= 26; i++) st.s[i] = 0;
  T.build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    int l = read(), r = read(), opt = read(), nl = l;
    Ans res = st;
    T.ask(1, l, r, res);
    if (opt == 1) {
      for (int j = 1; j <= 26; j++) {
        if (res.s[j]) {
          T.change(1, nl, nl + res.s[j] - 1, j);
        }
        nl += res.s[j];
      }
    } else {
      for (int j = 26; j >= 1; j--) {
        if (res.s[j]) {
          T.change(1, nl, nl + res.s[j] - 1, j);
        }
        nl += res.s[j];
      }
    }
  }
  for (int i = 1; i <= n; i++) cout << (char)(T.askp(1, i) + 'a' - 1);
  puts("");
  return 0;
}

### Prompt

Create a solution in CPP for 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;
struct xbk {
  int l, r, s[28], tag;
};
struct Ans {
  int s[28];
} st;
int n, m, a[(100010)];
string s;
inline int read() {
  int w = 0;
  char ch = getchar();
  while (ch > '9' || ch < '0') ch = getchar();
  while (ch >= '0' && ch <= '9') {
    w = (w << 3) + (w << 1) + (ch ^ 48);
    ch = getchar();
  }
  return w;
}
struct STree {
  xbk t[(400010)];
  inline void update(int p) {
    for (int i = 1; i <= 26; i++)
      t[p].s[i] = t[p << 1].s[i] + t[p << 1 | 1].s[i];
    return;
  }
  inline void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) {
      t[p].s[a[l]] = 1;
      return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    update(p);
    return;
  }
  inline void spread(int p) {
    if (!t[p].tag) return;
    for (int i = 1; i <= 26; i++) t[p << 1].s[i] = t[p << 1 | 1].s[i] = 0;
    t[p << 1].s[t[p].tag] = t[p << 1].r - t[p << 1].l + 1;
    t[p << 1 | 1].s[t[p].tag] = t[p << 1 | 1].r - t[p << 1 | 1].l + 1;
    t[p << 1].tag = t[p << 1 | 1].tag = t[p].tag;
    t[p].tag = 0;
  }
  inline void change(int p, int l, int r, int v) {
    if (t[p].l >= l && t[p].r <= r) {
      for (int i = 1; i <= 26; i++) t[p].s[i] = 0;
      t[p].s[v] = (t[p].r - t[p].l + 1), t[p].tag = v;
      return;
    }
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) change(p << 1, l, r, v);
    if (r > mid) change(p << 1 | 1, l, r, v);
    update(p);
    return;
  }
  inline void ask(int p, int l, int r, Ans &res) {
    if (t[p].l >= l && t[p].r <= r) {
      for (int i = 1; i <= 26; i++) res.s[i] += t[p].s[i];
      return;
    }
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) ask(p << 1, l, r, res);
    if (r > mid) ask(p << 1 | 1, l, r, res);
    update(p);
    return;
  }
  inline int askp(int p, int pos) {
    if (t[p].l == t[p].r) {
      for (int i = 1; i <= 26; i++)
        if (t[p].s[i]) return i;
      return 0;
    }
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (pos <= mid) return askp(p << 1, pos);
    if (pos > mid) return askp(p << 1 | 1, pos);
    return 0;
  }
} T;
int main() {
  n = read(), m = read();
  cin >> s;
  for (int i = 0; i < n; i++) a[i + 1] = s[i] - 'a' + 1;
  for (int i = 1; i <= 26; i++) st.s[i] = 0;
  T.build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    int l = read(), r = read(), opt = read(), nl = l;
    Ans res = st;
    T.ask(1, l, r, res);
    if (opt == 1) {
      for (int j = 1; j <= 26; j++) {
        if (res.s[j]) {
          T.change(1, nl, nl + res.s[j] - 1, j);
        }
        nl += res.s[j];
      }
    } else {
      for (int j = 26; j >= 1; j--) {
        if (res.s[j]) {
          T.change(1, nl, nl + res.s[j] - 1, j);
        }
        nl += res.s[j];
      }
    }
  }
  for (int i = 1; i <= n; i++) cout << (char)(T.askp(1, i) + 'a' - 1);
  puts("");
  return 0;
}

```