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 MAXN = 100005;
struct Node {
  int x, y;
  int num[26];
  int lazy;
} t[MAXN << 2];
int n, m;
char s[MAXN];
void Push_Up(int rt) {
  for (int i = 0; i < 26; i++) {
    t[rt].num[i] = t[rt << 1].num[i] + t[rt << 1 | 1].num[i];
  }
}
void Push_Down(int rt) {
  if (t[rt].lazy != -1) {
    t[rt << 1].lazy = t[rt << 1 | 1].lazy = t[rt].lazy;
    memset(t[rt << 1].num, 0, sizeof(t[rt << 1].num));
    memset(t[rt << 1 | 1].num, 0, sizeof(t[rt << 1 | 1].num));
    t[rt << 1].num[t[rt].lazy] = t[rt << 1].y - t[rt << 1].x + 1;
    t[rt << 1 | 1].num[t[rt].lazy] = t[rt << 1 | 1].y - t[rt << 1 | 1].x + 1;
    t[rt].lazy = -1;
  }
}
void Build(int x, int y, int rt) {
  t[rt].x = x;
  t[rt].y = y;
  t[rt].lazy = -1;
  if (x == y) {
    memset(t[rt].num, 0, sizeof(t[rt].num));
    t[rt].num[s[x] - 'a']++;
    return;
  }
  int mid = (x + y) >> 1;
  Build(x, mid, rt << 1);
  Build(mid + 1, y, rt << 1 | 1);
  Push_Up(rt);
}
void Update(int rt, int left, int right, int lazy) {
  if (t[rt].x >= left && t[rt].y <= right) {
    memset(t[rt].num, 0, sizeof(t[rt].num));
    t[rt].lazy = lazy;
    t[rt].num[lazy] = t[rt].y - t[rt].x + 1;
    return;
  }
  int mid = (t[rt].x + t[rt].y) >> 1;
  Push_Down(rt);
  if (mid >= left) {
    Update(rt << 1, left, right, lazy);
  }
  if (mid < right) {
    Update(rt << 1 | 1, left, right, lazy);
  }
  Push_Up(rt);
}
int temp_num[26];
void Query(int rt, int left, int right) {
  if (t[rt].x >= left && t[rt].y <= right) {
    for (int i = 0; i < 26; i++) {
      temp_num[i] += t[rt].num[i];
    }
    return;
  }
  int mid = (t[rt].x + t[rt].y) >> 1;
  Push_Down(rt);
  if (mid >= left) {
    Query(rt << 1, left, right);
  }
  if (mid < right) {
    Query(rt << 1 | 1, left, right);
  }
  Push_Up(rt);
}
void Tree_print(int rt) {
  if (t[rt].x == t[rt].y) {
    for (int i = 0; i < 26; i++) {
      if (t[rt].num[i]) printf("%c", i + 'a');
    }
    return;
  }
  Push_Down(rt);
  Tree_print(rt << 1);
  Tree_print(rt << 1 | 1);
  Push_Up(rt);
}
void input() {
  memset(t, 0, sizeof(t));
  scanf("%s", s + 1);
  Build(1, n, 1);
  int x, y, r;
  for (int i = 1; i <= m; i++) {
    scanf("%d %d %d", &x, &y, &r);
    memset(temp_num, 0, sizeof(temp_num));
    Query(1, x, y);
    if (r == 1) {
      for (int i = 0; i < 26; i++) {
        if (temp_num[i]) {
          Update(1, x, x + temp_num[i] - 1, i);
          x = x + temp_num[i];
        }
      }
    } else {
      for (int i = 0; i < 26; i++) {
        if (temp_num[i]) {
          Update(1, y - temp_num[i] + 1, y, i);
          y = y - temp_num[i];
        }
      }
    }
  }
  Tree_print(1);
  puts("");
}
void solve() {}
int main(void) {
  while (~scanf("%d %d", &n, &m)) {
    input();
    solve();
  }
  return 0;
}