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 Segment_Tree_Node {
  Segment_Tree_Node *left, *right;
  int l, r, mid;
  int val;
  Segment_Tree_Node(int, int);
  ~Segment_Tree_Node();
};
Segment_Tree_Node::Segment_Tree_Node(int ll, int rr) {
  l = ll;
  r = rr;
  mid = (l + r) / 2;
  val = 0;
  if (r > l) {
    left = new Segment_Tree_Node(l, mid);
    right = new Segment_Tree_Node(mid + 1, r);
    val = -1;
  }
}
Segment_Tree_Node::~Segment_Tree_Node() {
  if (l < r) {
    delete left;
    delete right;
  }
}
char t[100001];
Segment_Tree_Node* alt[26];
void assign(Segment_Tree_Node* p, int l, int r, int val) {
  if (r < l) return;
  if (p->val == val) return;
  if (l == p->l && r == p->r) {
    p->val = val;
    return;
  }
  if (p->val == 1 - val) {
    p->val = -1;
    if (l > p->l) assign(p, p->l, l - 1, 1 - val);
    if (r < p->r) assign(p, r + 1, p->r, 1 - val);
  }
  if (r <= p->mid) {
    assign(p->left, l, r, val);
  } else if (l > p->mid) {
    assign(p->right, l, r, val);
  } else {
    assign(p->left, l, p->mid, val);
    assign(p->right, p->mid + 1, r, val);
  }
}
int count(Segment_Tree_Node* p, int l, int r) {
  if (p->val != -1) return (r - l + 1) * p->val;
  if (r <= p->mid)
    return count(p->left, l, r);
  else if (l > p->mid)
    return count(p->right, l, r);
  else
    return count(p->left, l, p->mid) + count(p->right, p->mid + 1, r);
}
int main() {
  ios::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  cin >> t;
  int l, r, k, sum;
  int tmp[26];
  for (int i = 0; i < 26; i++) alt[i] = new Segment_Tree_Node(0, n - 1);
  for (int i = 0; i < n; i++) assign(alt[t[i] - 'a'], i, i, 1);
  for (int i = 0; i < q; i++) {
    cin >> l >> r >> k;
    sum = 0;
    l--;
    r--;
    for (int j = 0; j < 26; j++) tmp[j] = count(alt[j], l, r);
    if (k) {
      for (int j = 0; j < 26; j++)
        if (tmp[j]) {
          assign(alt[j], l, r, 0);
          assign(alt[j], l + sum, l + sum + tmp[j] - 1, 1);
          sum += tmp[j];
        }
    } else {
      for (int j = 25; j >= 0; j--)
        if (tmp[j]) {
          assign(alt[j], l, r, 0);
          assign(alt[j], l + sum, l + sum + tmp[j] - 1, 1);
          sum += tmp[j];
        }
    }
  }
  for (int k = 0; k < n; k++) {
    for (int j = 0; j < 26; j++)
      if (count(alt[j], k, k)) {
        cout << (char)('a' + j);
        break;
      }
  }
  cout << endl;
  for (int i = 0; i < 26; i++) delete alt[i];
  return 0;
}