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;
string s;
class Segtree {
 public:
  Segtree(int n, char cc) {
    c = cc;
    size = n;
    tree = new int[n << 3];
    lazy = new int[n << 3];
    build(1, 0, size - 1);
  }
  void update(int start, int end, int value) {
    update(1, 0, size - 1, start, end, value);
  }
  int query(int start, int end) { return query(1, 0, size - 1, start, end); }
  int size, *tree, *lazy;
  char c;
  int outOfRange = 0, defaultLazyValue = -1;
  inline int merge(int a, int b) { return a + b; }
  inline void updateNodeFromLazy(int& node, int& start, int& end) {
    tree[node] = lazy[node] * (end - start + 1);
  }
  inline void updateChildrenLazy(int& node, int& start, int& end) {
    int into2 = node << 1;
    lazy[into2] = lazy[node];
    lazy[into2 + 1] = lazy[node];
  }
  inline void clearLazy(int& node, int& start, int& end) {
    lazy[node] = defaultLazyValue;
  }
  inline void updateNodeByValue(int& node, int& start, int& end, int& value) {
    tree[node] = value * (end - start + 1);
  }
  inline void updateLazyByValue(int& node, int& start, int& end, int& into2,
                                int& value) {
    lazy[into2] = value;
    lazy[into2 + 1] = value;
  }
  void build(int node, int start, int end) {
    int into2 = node << 1, mid = (start + end) / 2;
    if (start == end) {
      tree[node] = s[start] == c;
      lazy[node] = defaultLazyValue;
    } else {
      build(into2, start, mid), build(into2 + 1, mid + 1, end);
      lazy[node] = defaultLazyValue;
      tree[node] = merge(tree[into2], tree[into2 + 1]);
    }
  }
  void push(int node, int start, int end) {
    if (lazy[node] != defaultLazyValue) {
      updateNodeFromLazy(node, start, end);
      if (start != end) updateChildrenLazy(node, start, end);
      clearLazy(node, start, end);
    }
  }
  void update(int node, int start, int end, int rangestart, int rangeend,
              int value) {
    int into2 = node << 1, mid = (start + end) / 2;
    push(node, start, end);
    if (start > end || start > rangeend || end < rangestart) return;
    if (rangestart <= start && end <= rangeend) {
      updateNodeByValue(node, start, end, value);
      if (start != end) updateLazyByValue(node, start, end, into2, value);
      return;
    }
    update(into2, start, mid, rangestart, rangeend, value),
        update(into2 + 1, mid + 1, end, rangestart, rangeend, value);
    tree[node] = merge(tree[into2], tree[into2 + 1]);
  }
  int query(int node, int start, int end, int rangestart, int rangeend) {
    int into2 = node << 1, mid = (start + end) / 2;
    if (start > end || start > rangeend || end < rangestart) return outOfRange;
    push(node, start, end);
    if (rangestart <= start && end <= rangeend) return tree[node];
    return merge(query(into2, start, mid, rangestart, rangeend),
                 query(into2 + 1, mid + 1, end, rangestart, rangeend));
  }
};
int n;
Segtree* S[26];
void printSTR() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 26; j++) {
      if (S[j]->query(i, i)) cout << ((char)('a' + j));
    }
  }
  cout << endl;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  ;
  int q, l, r, k;
  cin >> n >> q >> s;
  for (int i = 0; i < 26; i++) {
    S[i] = new Segtree(s.size(), 'a' + i);
  }
  for (int i = 0; i < q; i++) {
    cin >> l >> r >> k;
    l--;
    r--;
    vector<int> count(26, 0);
    for (int i = 0; i < 26; i++) count[i] = S[i]->query(l, r);
    for (int i = 0; i < 26; i++) S[i]->update(l, r, 0);
    int used = 0;
    if (k == 1) {
      for (int i = 0; i < 26; i++) {
        S[i]->update(l + used, l + used + count[i] - 1, 1);
        used += count[i];
      }
    } else {
      for (int i = 0; i < 26; i++) {
        S[25 - i]->update(l + used, l + used + count[25 - i] - 1, 1);
        used += count[25 - i];
      }
    }
  }
  printSTR();
  return 0;
}