#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << " " << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
void inp_out() {}
long long int ar[100005];
struct SegmentTree {
  long long int n;
  vector<long long int> v, lazy;
  void init(long long int sz) {
    n = sz;
    sz = 4 * n + 1;
    v.clear();
    lazy.clear();
    v.resize(sz, 0);
    lazy.resize(sz, -1);
  }
  void build(long long int ipos, long long int fpos, long long int pos = 1) {
    if (ipos > fpos) return;
    if (ipos == fpos) {
      v[pos] = ar[ipos];
    } else {
      long long int mid = (ipos + fpos) / 2;
      build(ipos, mid, pos * 2);
      build(mid + 1, fpos, pos * 2 + 1);
      v[pos] = v[pos * 2] + v[pos * 2 + 1];
    }
  }
  long long int query(long long int l, long long int r, long long int ipos,
                      long long int fpos, long long int pos = 1) {
    if (ipos > fpos) return 0;
    if (l > r) return 0;
    if (lazy[pos] != -1) {
      v[pos] = (fpos - ipos + 1) * lazy[pos];
      if (ipos != fpos) {
        lazy[pos * 2] = lazy[pos];
        lazy[pos * 2 + 1] = lazy[pos];
      }
      lazy[pos] = -1;
    }
    long long int mid = (ipos + fpos) / 2;
    if ((l == ipos) && (r == fpos))
      return v[pos];
    else
      return query(l, min(mid, r), ipos, mid, pos * 2) +
             query(max(mid + 1, l), r, mid + 1, fpos, pos * 2 + 1);
  }
  void updateRangeUtil(long long int l, long long int r, long long int val,
                       long long int ipos, long long int fpos,
                       long long int pos = 1) {
    if (lazy[pos] != -1) {
      v[pos] = (fpos - ipos + 1) * lazy[pos];
      if (ipos != fpos) {
        lazy[pos * 2] = lazy[pos];
        lazy[pos * 2 + 1] = lazy[pos];
      }
      lazy[pos] = -1;
    }
    if (ipos > fpos || ipos > r || fpos < l) return;
    if (ipos >= l && fpos <= r) {
      v[pos] = (fpos - ipos + 1) * val;
      if (ipos != fpos) {
        lazy[pos * 2] = val;
        lazy[pos * 2 + 1] = val;
      }
      return;
    }
    int mid = (ipos + fpos) / 2;
    updateRangeUtil(l, r, val, ipos, mid, pos * 2);
    updateRangeUtil(l, r, val, mid + 1, fpos, pos * 2 + 1);
    v[pos] = v[pos * 2] + v[pos * 2 + 1];
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  inp_out();
  long long int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<vector<long long int>> a(26, vector<long long int>(n, 0));
  SegmentTree stree[26];
  for (long long int i = 0; i < 26; ++i) {
    for (long long int j = 0; j < n; ++j) {
      if (s[j] == (char)('a' + i))
        ar[j] = 1;
      else
        ar[j] = 0;
    }
    stree[i].init(n);
    stree[i].build(0, n - 1);
  }
  while (q--) {
    long long int l, r, k;
    cin >> l >> r >> k;
    --l, --r;
    long long int init = l, cnt = 0;
    if (k == 1)
      for (long long int i = 0; i < 26; ++i) {
        cnt = stree[i].query(l, r, 0, n - 1);
        stree[i].updateRangeUtil(l, r, 0, 0, n - 1);
        stree[i].updateRangeUtil(init, init + cnt - 1, 1, 0, n - 1);
        init += cnt;
      }
    else
      for (long long int i = 25; i >= 0; --i) {
        cnt = stree[i].query(l, r, 0, n - 1);
        stree[i].updateRangeUtil(l, r, 0, 0, n - 1);
        stree[i].updateRangeUtil(init, init + cnt - 1, 1, 0, n - 1);
        init += cnt;
      }
  }
  for (long long int i = 0; i < n; ++i) {
    for (long long int j = 0; j < 26; ++j) {
      if (stree[j].query(i, i, 0, n - 1)) {
        cout << (char)('a' + j);
        break;
      }
    }
  }
  return 0;
}

### 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;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << " " << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
void inp_out() {}
long long int ar[100005];
struct SegmentTree {
  long long int n;
  vector<long long int> v, lazy;
  void init(long long int sz) {
    n = sz;
    sz = 4 * n + 1;
    v.clear();
    lazy.clear();
    v.resize(sz, 0);
    lazy.resize(sz, -1);
  }
  void build(long long int ipos, long long int fpos, long long int pos = 1) {
    if (ipos > fpos) return;
    if (ipos == fpos) {
      v[pos] = ar[ipos];
    } else {
      long long int mid = (ipos + fpos) / 2;
      build(ipos, mid, pos * 2);
      build(mid + 1, fpos, pos * 2 + 1);
      v[pos] = v[pos * 2] + v[pos * 2 + 1];
    }
  }
  long long int query(long long int l, long long int r, long long int ipos,
                      long long int fpos, long long int pos = 1) {
    if (ipos > fpos) return 0;
    if (l > r) return 0;
    if (lazy[pos] != -1) {
      v[pos] = (fpos - ipos + 1) * lazy[pos];
      if (ipos != fpos) {
        lazy[pos * 2] = lazy[pos];
        lazy[pos * 2 + 1] = lazy[pos];
      }
      lazy[pos] = -1;
    }
    long long int mid = (ipos + fpos) / 2;
    if ((l == ipos) && (r == fpos))
      return v[pos];
    else
      return query(l, min(mid, r), ipos, mid, pos * 2) +
             query(max(mid + 1, l), r, mid + 1, fpos, pos * 2 + 1);
  }
  void updateRangeUtil(long long int l, long long int r, long long int val,
                       long long int ipos, long long int fpos,
                       long long int pos = 1) {
    if (lazy[pos] != -1) {
      v[pos] = (fpos - ipos + 1) * lazy[pos];
      if (ipos != fpos) {
        lazy[pos * 2] = lazy[pos];
        lazy[pos * 2 + 1] = lazy[pos];
      }
      lazy[pos] = -1;
    }
    if (ipos > fpos || ipos > r || fpos < l) return;
    if (ipos >= l && fpos <= r) {
      v[pos] = (fpos - ipos + 1) * val;
      if (ipos != fpos) {
        lazy[pos * 2] = val;
        lazy[pos * 2 + 1] = val;
      }
      return;
    }
    int mid = (ipos + fpos) / 2;
    updateRangeUtil(l, r, val, ipos, mid, pos * 2);
    updateRangeUtil(l, r, val, mid + 1, fpos, pos * 2 + 1);
    v[pos] = v[pos * 2] + v[pos * 2 + 1];
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  inp_out();
  long long int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<vector<long long int>> a(26, vector<long long int>(n, 0));
  SegmentTree stree[26];
  for (long long int i = 0; i < 26; ++i) {
    for (long long int j = 0; j < n; ++j) {
      if (s[j] == (char)('a' + i))
        ar[j] = 1;
      else
        ar[j] = 0;
    }
    stree[i].init(n);
    stree[i].build(0, n - 1);
  }
  while (q--) {
    long long int l, r, k;
    cin >> l >> r >> k;
    --l, --r;
    long long int init = l, cnt = 0;
    if (k == 1)
      for (long long int i = 0; i < 26; ++i) {
        cnt = stree[i].query(l, r, 0, n - 1);
        stree[i].updateRangeUtil(l, r, 0, 0, n - 1);
        stree[i].updateRangeUtil(init, init + cnt - 1, 1, 0, n - 1);
        init += cnt;
      }
    else
      for (long long int i = 25; i >= 0; --i) {
        cnt = stree[i].query(l, r, 0, n - 1);
        stree[i].updateRangeUtil(l, r, 0, 0, n - 1);
        stree[i].updateRangeUtil(init, init + cnt - 1, 1, 0, n - 1);
        init += cnt;
      }
  }
  for (long long int i = 0; i < n; ++i) {
    for (long long int j = 0; j < 26; ++j) {
      if (stree[j].query(i, i, 0, n - 1)) {
        cout << (char)('a' + j);
        break;
      }
    }
  }
  return 0;
}

```