#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1 << 17;
struct LazySegTree {
  int n;
  struct S {
    int t;
    int cnt[26];
    S() : t(-1) { memset(cnt, 0, sizeof cnt); }
  };
  S node[2 * MAX_N - 1];
  S sum;
  void init(int n_) {
    n = 1;
    while (n < n_) n *= 2;
  }
  void propagate(int k, int level) {
    if (node[k].t == -1) return;
    if (2 * k + 1 < 2 * n - 1) {
      S& l = node[2 * k + 1];
      S& r = node[2 * k + 2];
      l.t = r.t = node[k].t;
      for (int i = 0; i < 26; i++) {
        l.cnt[i] = l.cnt[i] = 0;
      }
      int rem = n >> (level + 1);
      for (int i = 0; i < 26; i++) {
        int x = node[k].t == 1 ? i : 25 - i;
        if (node[k].cnt[x] == 0) continue;
        int carry = min(node[k].cnt[x], rem);
        node[k].cnt[x] -= carry;
        l.cnt[x] += carry;
        rem -= carry;
        if (rem == 0) break;
      }
      for (int i = 0; i < 26; i++) {
        r.cnt[i] = node[k].cnt[i];
        node[k].cnt[i] += l.cnt[i];
      }
    }
    node[k].t = -1;
  }
  void marge(int k) {
    S& l = node[2 * k + 1];
    S& r = node[2 * k + 2];
    for (int i = 0; i < 26; i++) {
      node[k].cnt[i] = l.cnt[i] + r.cnt[i];
    }
  }
  void query(int a, int b, int t) { query(a, b, t, 0, 0, 0, n); }
  void query(int a, int b, int t, int level, int k, int l, int r) {
    propagate(k, level);
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      memset(node[k].cnt, 0, sizeof node[k].cnt);
      node[k].t = t;
      int rem = n >> level;
      for (int i = 0; i < 26; i++) {
        int x = t == 1 ? i : 25 - i;
        if (sum.cnt[x] == 0) continue;
        int carry = min(sum.cnt[x], rem);
        sum.cnt[x] -= carry;
        node[k].cnt[x] += carry;
        rem -= carry;
        if (rem == 0) break;
      }
      propagate(k, level);
      return;
    }
    query(a, b, t, level + 1, k * 2 + 1, l, (l + r) / 2);
    query(a, b, t, level + 1, k * 2 + 2, (l + r) / 2, r);
    marge(k);
  }
  void get_sum(int a, int b) {
    memset(sum.cnt, 0, sizeof sum.cnt);
    get_sum(a, b, 0, 0, 0, n);
  }
  void get_sum(int a, int b, int level, int k, int l, int r) {
    propagate(k, level);
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      for (int i = 0; i < 26; i++) {
        sum.cnt[i] += node[k].cnt[i];
      }
      return;
    }
    get_sum(a, b, level + 1, k * 2 + 1, l, (l + r) / 2);
    get_sum(a, b, level + 1, k * 2 + 2, (l + r) / 2, r);
  }
};
LazySegTree st;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  string s;
  cin >> n >> m >> s;
  st.init(n);
  for (int i = 0; i < n; i++) {
    int x = i + st.n - 1;
    st.node[x].cnt[s[i] - 'a']++;
  }
  for (int i = st.n - 2; i >= 0; i--) {
    st.marge(i);
  }
  while (m--) {
    int l, r, k;
    cin >> l >> r >> k;
    l--, r--;
    st.get_sum(l, r + 1);
    st.query(l, r + 1, k);
  }
  int level = 0;
  for (int i = 0; i < st.n - 2; i++) {
    if (i == (1 << (level + 1)) - 1) level++;
    st.propagate(i, level);
  }
  for (int i = 0; i < n; i++) {
    int x = i + st.n - 1;
    for (int j = 0; j < 26; j++) {
      if (st.node[x].cnt[j]) {
        cout << char('a' + j);
        break;
      }
    }
  }
  cout << endl;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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 MAX_N = 1 << 17;
struct LazySegTree {
  int n;
  struct S {
    int t;
    int cnt[26];
    S() : t(-1) { memset(cnt, 0, sizeof cnt); }
  };
  S node[2 * MAX_N - 1];
  S sum;
  void init(int n_) {
    n = 1;
    while (n < n_) n *= 2;
  }
  void propagate(int k, int level) {
    if (node[k].t == -1) return;
    if (2 * k + 1 < 2 * n - 1) {
      S& l = node[2 * k + 1];
      S& r = node[2 * k + 2];
      l.t = r.t = node[k].t;
      for (int i = 0; i < 26; i++) {
        l.cnt[i] = l.cnt[i] = 0;
      }
      int rem = n >> (level + 1);
      for (int i = 0; i < 26; i++) {
        int x = node[k].t == 1 ? i : 25 - i;
        if (node[k].cnt[x] == 0) continue;
        int carry = min(node[k].cnt[x], rem);
        node[k].cnt[x] -= carry;
        l.cnt[x] += carry;
        rem -= carry;
        if (rem == 0) break;
      }
      for (int i = 0; i < 26; i++) {
        r.cnt[i] = node[k].cnt[i];
        node[k].cnt[i] += l.cnt[i];
      }
    }
    node[k].t = -1;
  }
  void marge(int k) {
    S& l = node[2 * k + 1];
    S& r = node[2 * k + 2];
    for (int i = 0; i < 26; i++) {
      node[k].cnt[i] = l.cnt[i] + r.cnt[i];
    }
  }
  void query(int a, int b, int t) { query(a, b, t, 0, 0, 0, n); }
  void query(int a, int b, int t, int level, int k, int l, int r) {
    propagate(k, level);
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      memset(node[k].cnt, 0, sizeof node[k].cnt);
      node[k].t = t;
      int rem = n >> level;
      for (int i = 0; i < 26; i++) {
        int x = t == 1 ? i : 25 - i;
        if (sum.cnt[x] == 0) continue;
        int carry = min(sum.cnt[x], rem);
        sum.cnt[x] -= carry;
        node[k].cnt[x] += carry;
        rem -= carry;
        if (rem == 0) break;
      }
      propagate(k, level);
      return;
    }
    query(a, b, t, level + 1, k * 2 + 1, l, (l + r) / 2);
    query(a, b, t, level + 1, k * 2 + 2, (l + r) / 2, r);
    marge(k);
  }
  void get_sum(int a, int b) {
    memset(sum.cnt, 0, sizeof sum.cnt);
    get_sum(a, b, 0, 0, 0, n);
  }
  void get_sum(int a, int b, int level, int k, int l, int r) {
    propagate(k, level);
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      for (int i = 0; i < 26; i++) {
        sum.cnt[i] += node[k].cnt[i];
      }
      return;
    }
    get_sum(a, b, level + 1, k * 2 + 1, l, (l + r) / 2);
    get_sum(a, b, level + 1, k * 2 + 2, (l + r) / 2, r);
  }
};
LazySegTree st;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  string s;
  cin >> n >> m >> s;
  st.init(n);
  for (int i = 0; i < n; i++) {
    int x = i + st.n - 1;
    st.node[x].cnt[s[i] - 'a']++;
  }
  for (int i = st.n - 2; i >= 0; i--) {
    st.marge(i);
  }
  while (m--) {
    int l, r, k;
    cin >> l >> r >> k;
    l--, r--;
    st.get_sum(l, r + 1);
    st.query(l, r + 1, k);
  }
  int level = 0;
  for (int i = 0; i < st.n - 2; i++) {
    if (i == (1 << (level + 1)) - 1) level++;
    st.propagate(i, level);
  }
  for (int i = 0; i < n; i++) {
    int x = i + st.n - 1;
    for (int j = 0; j < 26; j++) {
      if (st.node[x].cnt[j]) {
        cout << char('a' + j);
        break;
      }
    }
  }
  cout << endl;
}

```