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;
struct segtree {
  vector<vector<int>> t;
  vector<int> d;
  int h, n, sz;
  inline void build_node(const int& x) {
    for (int j = 0; j < 26; ++j) {
      t[x][j] = t[x << 1][j] + t[x << 1 | 1][j];
    }
  }
  inline void build(int x) {
    for (x /= 2; x > 0; x /= 2) {
      build_node(x);
    }
  }
  segtree(const string& s) {
    sz = s.size();
    h = sizeof(int) * 8 - __builtin_clz(sz);
    n = 1 << h;
    d = vector<int>(n << 1, 0);
    t = vector<vector<int>>(n << 1, vector<int>(26, 0));
    for (int i = 0; i < sz; ++i) {
      ++t[i + n][s[i] - 'a'];
    }
    for (int i = n - 1; i > 0; --i) {
      build_node(i);
    }
  }
  void apply(int x, int v) {
    if (x < n) {
      d[x] = v;
    }
  }
  void fill_nodes(const vector<int>& ind, const vector<int>& char_count,
                  int dir) {
    for (const int& x : ind) {
      for (int i = 0; i < 26; ++i) {
        t[x][i] = 0;
      }
    }
    int ch_type = (dir == 1 ? 0 : 25);
    int used_of_type = 0;
    for (int i = (dir == 1 ? 0 : 0); i < ind.size(); ++i) {
      int x = ind[i];
      int my_sz = 1 << (h - (sizeof(int) * 8 - __builtin_clz(x)) + 1);
      int have = 0;
      for (; have < my_sz; (dir == 1 ? ++ch_type : --ch_type)) {
        int take = min(my_sz - have, char_count[ch_type] - used_of_type);
        t[x][ch_type] += take;
        have += take;
        used_of_type += take;
        if (have == my_sz) break;
        used_of_type = 0;
      }
    }
  }
  void sort_nodes(const vector<int>& ind, int dir) {
    vector<int> char_count(26, 0);
    for (const int& x : ind) {
      for (int i = 0; i < 26; ++i) {
        char_count[i] += t[x][i];
      }
    }
    fill_nodes(ind, char_count, dir);
  }
  void push_node(int x) {
    if (d[x] != 0) {
      fill_nodes(vector<int>({x << 1, x << 1 | 1}), t[x], d[x]);
      apply(x << 1, d[x]);
      apply(x << 1 | 1, d[x]);
      d[x] = 0;
    }
  }
  void push(int x) {
    for (int s = h; s > 0; --s) {
      int i = x >> s;
      if (d[i] != 0) {
        push_node(i);
      }
    }
  }
  void set(int l, int r, int dir) {
    int l0 = l + n;
    int r0 = r + n;
    push(l0);
    push(r0 - 1);
    vector<int> front, back;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l % 2) {
        front.push_back(l);
        apply(l, dir);
        ++l;
      }
      if (r % 2) {
        --r;
        back.push_back(r);
        apply(r, dir);
      }
    }
    reverse(back.begin(), back.end());
    front.insert(front.end(), back.begin(), back.end());
    sort_nodes(front, dir);
    push(l0);
    push(r0 - 1);
    build(l0);
    build(r0 - 1);
  }
  string to_string() {
    for (int i = 1; i < n; ++i) {
      push_node(i);
    }
    static char cstr[100010];
    for (int i = 0; i < sz; ++i) {
      for (int j = 0; j < 26; ++j) {
        if (t[i + n][j] != 0) {
          cstr[i] = j + 'a';
        }
      }
    }
    cstr[sz] = 0;
    return string(cstr);
  }
};
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int N, Q;
  cin >> N >> Q;
  string s;
  cin >> s;
  segtree st(s);
  for (int qq = 0; qq < Q; ++qq) {
    int i, j, k;
    cin >> i >> j >> k;
    st.set(i - 1, j, (k == 1 ? 1 : -1));
  }
  cout << st.to_string() << "\n";
  return 0;
}