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;
const int MAX = 100010;
const int MAX_V = 28;
class Node {
 public:
  int l, r, v[MAX_V];
  Node();
  int mid() { return (l + r) / 2; }
  int len() { return r - l + 1; }
};
int Lazy[MAX * 4][MAX_V];
int N, Q;
char str[MAX];
Node tree[MAX * 4];
void PushUp(int k, int id) {
  tree[k].v[id] = tree[(k * 2)].v[id] + tree[(k * 2 + 1)].v[id];
}
void PushDown(int k, int id) {
  if (Lazy[k][id] != -1) {
    int value = Lazy[k][id];
    tree[(k * 2)].v[id] = tree[(k * 2)].len() * value;
    tree[(k * 2 + 1)].v[id] = tree[(k * 2 + 1)].len() * value;
    Lazy[(k * 2)][id] = value;
    Lazy[(k * 2 + 1)][id] = value;
  }
  Lazy[k][id] = -1;
}
void Build(int L, int R, int k) {
  tree[k].l = L;
  tree[k].r = R;
  if (L == R) {
    int id = str[L] - 'a';
    tree[k].v[id] = 1;
    return;
  }
  int mid = (L + R) / 2;
  Build(L, mid, (k * 2));
  Build(mid + 1, R, (k * 2 + 1));
  for (int i = 0; i < 26; ++i) PushUp(k, i);
}
void Update(int L, int R, int add, int k, int id) {
  if (L <= tree[k].l && tree[k].r <= R) {
    tree[k].v[id] = add * tree[k].len();
    Lazy[k][id] = add;
    return;
  }
  PushDown(k, id);
  int mid = tree[k].mid();
  if (L <= mid) Update(L, R, add, (k * 2), id);
  if (R > mid) Update(L, R, add, (k * 2 + 1), id);
  PushUp(k, id);
}
int Query(int L, int R, int k, int id) {
  if (L <= tree[k].l && tree[k].r <= R) return tree[k].v[id];
  PushDown(k, id);
  int res = 0;
  int mid = tree[k].mid();
  if (L <= mid) res += Query(L, R, (k * 2), id);
  if (R > mid) res += Query(L, R, (k * 2 + 1), id);
  return res;
}
void Display() {
  for (int i = 1; i <= N; ++i) {
    for (int id = 0; id < 26; ++id) {
      if (Query(i, i, 1, id)) {
        printf("%c", 'a' + id);
      }
    }
  }
  printf("\n");
}
void Show(int *bas) {
  for (int id = 0; id < 26; ++id) {
    printf("%d ", bas[id]);
  }
  printf("\n");
}
int main(void) {
  memset(Lazy, -1, sizeof(Lazy));
  scanf("%d%d", &N, &Q);
  scanf("%s", str + 1);
  Build(1, N, 1);
  int u, v, w;
  int bas[MAX_V];
  for (int i = 1; i <= Q; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    if (w == 0) {
      for (int id = 0; id < 26; ++id) {
        bas[id] = Query(u, v, 1, id);
        Update(u, v, 0, 1, id);
      }
      int l = u, r;
      for (int id = 25; id >= 0; --id) {
        if (bas[id]) {
          r = l + bas[id] - 1;
          Update(l, r, 1, 1, id);
          l += bas[id];
        }
      }
    } else {
      for (int id = 0; id < 26; ++id) {
        bas[id] = Query(u, v, 1, id);
        Update(u, v, 0, 1, id);
      }
      int l = u, r;
      for (int id = 0; id < 26; ++id) {
        if (bas[id]) {
          r = l + bas[id] - 1;
          Update(l, r, 1, 1, id);
          l += bas[id];
        }
      }
    }
  }
  Display();
  return 0;
}
Node::Node() {
  l = r = 0;
  memset(v, 0, sizeof(v));
}