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>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int n, L, R, k, len;
struct Node {
  int l, r, alpha;
  bool operator<(const Node nd) const { return l < nd.l; }
};
set<Node> st;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> len >> n;
  cin >> s;
  for (int i = 0; i < s.length(); i++) {
    st.insert({i + 1, i + 1, s[i] - 'a'});
  }
  st.insert({len + 1, len + 1, 50});
  for (int i = 0; i < n; i++) {
    cin >> L >> R >> k;
    int cnt[26] = {
        0,
    };
    auto jt = st.lower_bound({L, 0, 0});
    if (jt->l != L) {
      jt--;
      int ll = jt->l;
      int rr = jt->r;
      int alpha = jt->alpha;
      st.erase(jt);
      st.insert({ll, L - 1, alpha});
      st.insert({L, rr, alpha});
    }
    jt = st.upper_bound({R, R, 25});
    if (jt->r != R + 1) {
      jt--;
      int ll = jt->l;
      int rr = jt->r;
      int alpha = jt->alpha;
      st.erase(jt);
      st.insert({ll, R, alpha});
      st.insert({R + 1, rr, alpha});
    }
    auto ed = st.upper_bound({R, R, 25});
    for (auto it = st.lower_bound({L, 0, 0}); it != ed;) {
      jt = it;
      jt++;
      cnt[it->alpha] += (it->r - it->l + 1);
      st.erase(it);
      it = jt;
    }
    if (k == 1) {
      for (int i = 0; i < 26; i++) {
        if (cnt[i]) st.insert({L, L + cnt[i] - 1, i});
        L += cnt[i];
      }
    } else {
      for (int i = 25; i >= 0; i--) {
        if (cnt[i]) st.insert({L, L + cnt[i] - 1, i});
        L += cnt[i];
      }
    }
  }
  auto ed = st.end();
  ed--;
  for (auto it = st.begin(); it != ed; it++) {
    int sz = it->r - it->l + 1;
    int alpha = it->alpha;
    for (int i = 0; i < sz; i++) cout << (char)(alpha + 'a');
  }
  return 0;
}