#include <bits/stdc++.h>
using namespace std;
struct node {
  long long val, op, opVal;
  void applyAdd(long long l, long long r, long long v) {
    val += ((r - l) * v);
    if (r - l > 1) {
      opVal += v;
      if (op != 2) op = 1;
    }
  }
  void applyAssign(long long l, long long r, long long v) {
    val = (r - l) * v;
    if (r - l > 1) {
      opVal = v;
      op = 2;
    }
  }
};
struct seg_tree {
  node NEUTRAL_ELEMENT = {0, 0, 0};
  node merge(const node &lc, const node &rc) {
    node res;
    res.val = lc.val + rc.val;
    res.opVal = 0;
    res.op = 0;
    return res;
  }
  void push(long long x, long long lx, long long rx) {
    long long mx = (rx - lx) / 2 + lx;
    if (st[x].op == 1) {
      st[lcx(x)].applyAdd(lx, mx, st[x].opVal);
      st[rcx(x)].applyAdd(mx, rx, st[x].opVal);
      st[x].opVal = 0;
      st[x].op = 0;
    } else if (st[x].op == 2) {
      st[lcx(x)].applyAssign(lx, mx, st[x].opVal);
      st[rcx(x)].applyAssign(mx, rx, st[x].opVal);
      st[x].opVal = 0;
      st[x].op = 0;
    }
  }
  void pull(long long x) { st[x] = merge(st[lcx(x)], st[rcx(x)]); }
  long long size;
  vector<node> st;
  long long lcx(long long x) { return 2 * x + 1; }
  long long rcx(long long x) { return 2 * x + 2; }
  void init(long long n) {
    size = 1;
    while (size < n) size *= 2;
    st.assign(2 * size, NEUTRAL_ELEMENT);
    build(0, 0, size);
  }
  void build(long long x, long long lx, long long rx) {
    if (rx - lx == 1) return;
    long long mx = (rx - lx) / 2 + lx;
    build(lcx(x), lx, mx);
    build(rcx(x), mx, rx);
    pull(x);
  }
  node query(long long i) { return query_recur(0, 0, size, i, i + 1); }
  node query(long long l, long long r) { return query_recur(0, 0, size, l, r); }
  node query_recur(long long x, long long lx, long long rx, long long l,
                   long long r) {
    push(x, lx, rx);
    if (lx >= l && rx <= r) return st[x];
    long long mx = (rx - lx) / 2 + lx;
    node res;
    if (r <= mx)
      res = query_recur(lcx(x), lx, mx, l, r);
    else {
      if (l >= mx)
        res = query_recur(rcx(x), mx, rx, l, r);
      else
        res = merge(query_recur(lcx(x), lx, mx, l, r),
                    query_recur(rcx(x), mx, rx, l, r));
    }
    pull(x);
    return res;
  }
  template <typename... M>
  void update(long long l, long long r, long long k, const M &...v) {
    update_recur(0LL, 0, size, l, r, k, v...);
  }
  template <typename... M>
  void update_recur(long long x, long long lx, long long rx, long long l,
                    long long r, long long k, const M &...v) {
    if (lx >= r || rx <= l) return;
    push(x, lx, rx);
    if (lx >= l && rx <= r) {
      (k == 1) ? st[x].applyAssign(lx, rx, v...) : st[x].applyAdd(lx, rx, v...);
      return;
    }
    long long mx = (rx - lx) / 2 + lx;
    update_recur(lcx(x), lx, mx, l, r, k, v...);
    update_recur(rcx(x), mx, rx, l, r, k, v...);
    pull(x);
  }
  void print() {
    for (int i = 0; i < st.size(); ++i) {
      cout << i << " -> { val: " << st[i].val << " , op: " << st[i].op
           << " , opVal: " << st[i].opVal << " } \n";
    }
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long t, n, q, i, j, k;
  cin >> n >> q;
  vector<seg_tree> a(26);
  for (i = 0; i < 26; i++) a[i].init(n);
  string s;
  cin >> s;
  for (i = 0; i < n; i++) a[s[i] - 'a'].update(i, i + 1, 2, 1);
  while (q--) {
    cin >> i >> j >> k;
    i--;
    vector<int> f(26, 0);
    for (int x = 0; x < 26; ++x) {
      f[x] = a[x].query(i, j).val;
      a[x].update(i, j, 1, 0);
    }
    int c = i;
    if (k) {
      for (int x = 0; x < 26; ++x) {
        if (!f[x]) continue;
        a[x].update(c, c + f[x], 2, 1);
        c += f[x];
      }
    } else {
      for (int x = 25; x >= 0; x--) {
        if (!f[x]) continue;
        a[x].update(c, c + f[x], 2, 1);
        c += f[x];
      }
    }
  }
  for (i = 0; i < n; i++) {
    for (j = 0; j < 26; j++) {
      k = a[j].query(i, i + 1).val;
      if (k == 1) {
        s[i] = j + 'a';
        break;
      }
    }
  }
  cout << s;
  return 0;
}

### Prompt

Please provide a Cpp coded solution 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;
struct node {
  long long val, op, opVal;
  void applyAdd(long long l, long long r, long long v) {
    val += ((r - l) * v);
    if (r - l > 1) {
      opVal += v;
      if (op != 2) op = 1;
    }
  }
  void applyAssign(long long l, long long r, long long v) {
    val = (r - l) * v;
    if (r - l > 1) {
      opVal = v;
      op = 2;
    }
  }
};
struct seg_tree {
  node NEUTRAL_ELEMENT = {0, 0, 0};
  node merge(const node &lc, const node &rc) {
    node res;
    res.val = lc.val + rc.val;
    res.opVal = 0;
    res.op = 0;
    return res;
  }
  void push(long long x, long long lx, long long rx) {
    long long mx = (rx - lx) / 2 + lx;
    if (st[x].op == 1) {
      st[lcx(x)].applyAdd(lx, mx, st[x].opVal);
      st[rcx(x)].applyAdd(mx, rx, st[x].opVal);
      st[x].opVal = 0;
      st[x].op = 0;
    } else if (st[x].op == 2) {
      st[lcx(x)].applyAssign(lx, mx, st[x].opVal);
      st[rcx(x)].applyAssign(mx, rx, st[x].opVal);
      st[x].opVal = 0;
      st[x].op = 0;
    }
  }
  void pull(long long x) { st[x] = merge(st[lcx(x)], st[rcx(x)]); }
  long long size;
  vector<node> st;
  long long lcx(long long x) { return 2 * x + 1; }
  long long rcx(long long x) { return 2 * x + 2; }
  void init(long long n) {
    size = 1;
    while (size < n) size *= 2;
    st.assign(2 * size, NEUTRAL_ELEMENT);
    build(0, 0, size);
  }
  void build(long long x, long long lx, long long rx) {
    if (rx - lx == 1) return;
    long long mx = (rx - lx) / 2 + lx;
    build(lcx(x), lx, mx);
    build(rcx(x), mx, rx);
    pull(x);
  }
  node query(long long i) { return query_recur(0, 0, size, i, i + 1); }
  node query(long long l, long long r) { return query_recur(0, 0, size, l, r); }
  node query_recur(long long x, long long lx, long long rx, long long l,
                   long long r) {
    push(x, lx, rx);
    if (lx >= l && rx <= r) return st[x];
    long long mx = (rx - lx) / 2 + lx;
    node res;
    if (r <= mx)
      res = query_recur(lcx(x), lx, mx, l, r);
    else {
      if (l >= mx)
        res = query_recur(rcx(x), mx, rx, l, r);
      else
        res = merge(query_recur(lcx(x), lx, mx, l, r),
                    query_recur(rcx(x), mx, rx, l, r));
    }
    pull(x);
    return res;
  }
  template <typename... M>
  void update(long long l, long long r, long long k, const M &...v) {
    update_recur(0LL, 0, size, l, r, k, v...);
  }
  template <typename... M>
  void update_recur(long long x, long long lx, long long rx, long long l,
                    long long r, long long k, const M &...v) {
    if (lx >= r || rx <= l) return;
    push(x, lx, rx);
    if (lx >= l && rx <= r) {
      (k == 1) ? st[x].applyAssign(lx, rx, v...) : st[x].applyAdd(lx, rx, v...);
      return;
    }
    long long mx = (rx - lx) / 2 + lx;
    update_recur(lcx(x), lx, mx, l, r, k, v...);
    update_recur(rcx(x), mx, rx, l, r, k, v...);
    pull(x);
  }
  void print() {
    for (int i = 0; i < st.size(); ++i) {
      cout << i << " -> { val: " << st[i].val << " , op: " << st[i].op
           << " , opVal: " << st[i].opVal << " } \n";
    }
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long t, n, q, i, j, k;
  cin >> n >> q;
  vector<seg_tree> a(26);
  for (i = 0; i < 26; i++) a[i].init(n);
  string s;
  cin >> s;
  for (i = 0; i < n; i++) a[s[i] - 'a'].update(i, i + 1, 2, 1);
  while (q--) {
    cin >> i >> j >> k;
    i--;
    vector<int> f(26, 0);
    for (int x = 0; x < 26; ++x) {
      f[x] = a[x].query(i, j).val;
      a[x].update(i, j, 1, 0);
    }
    int c = i;
    if (k) {
      for (int x = 0; x < 26; ++x) {
        if (!f[x]) continue;
        a[x].update(c, c + f[x], 2, 1);
        c += f[x];
      }
    } else {
      for (int x = 25; x >= 0; x--) {
        if (!f[x]) continue;
        a[x].update(c, c + f[x], 2, 1);
        c += f[x];
      }
    }
  }
  for (i = 0; i < n; i++) {
    for (j = 0; j < 26; j++) {
      k = a[j].query(i, i + 1).val;
      if (k == 1) {
        s[i] = j + 'a';
        break;
      }
    }
  }
  cout << s;
  return 0;
}

```