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;
int read() {
  int s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = (s << 3) + (s << 1) + ch - '0';
    ch = getchar();
  }
  return s * f;
}
int n, q, x, y, op;
char st[1000066];
int sum[1000066][30], add[1000066][30];
void build(int id, int l, int r, int rt) {
  add[rt][id] = -1;
  if (l == r) {
    if (st[l] == char(id - 1 + 'a')) sum[rt][id] = 1;
    return;
  }
  int mi = (l + r) >> 1;
  build(id, l, mi, rt << 1);
  build(id, mi + 1, r, rt << 1 | 1);
  sum[rt][id] = sum[rt << 1][id] + sum[rt << 1 | 1][id];
}
void pushdown(int rt, int ml, int mr, int id) {
  if (add[rt][id] >= 0) {
    sum[rt << 1][id] = ml * add[rt][id];
    sum[rt << 1 | 1][id] = mr * add[rt][id];
    add[rt << 1][id] = add[rt][id];
    add[rt << 1 | 1][id] = add[rt][id];
    add[rt][id] = -1;
  }
  return;
}
void update(int L, int R, int id, int C, int l, int r, int rt) {
  if (l >= L && r <= R) {
    sum[rt][id] = C * (r - l + 1);
    add[rt][id] = C;
    return;
  }
  int mi = (l + r) >> 1;
  pushdown(rt, mi - l + 1, r - mi, id);
  if (L <= mi) update(L, R, id, C, l, mi, rt << 1);
  if (R > mi) update(L, R, id, C, mi + 1, r, rt << 1 | 1);
  sum[rt][id] = sum[rt << 1][id] + sum[rt << 1 | 1][id];
  return;
}
int Query(int L, int R, int id, int l, int r, int rt) {
  if (l >= L && r <= R) return sum[rt][id];
  int mi = (l + r) >> 1, ans = 0;
  pushdown(rt, mi - l + 1, r - mi, id);
  if (L <= mi) ans += Query(L, R, id, l, mi, rt << 1);
  if (R > mi) ans += Query(L, R, id, mi + 1, r, rt << 1 | 1);
  return ans;
}
void final(int l, int r, int rt, int id) {
  if (l == r) {
    if (sum[rt][id] == 1) st[l] = char(id - 1 + 'a');
    return;
  }
  int mi = (l + r) >> 1;
  pushdown(rt, mi - l + 1, r - mi, id);
  final(l, mi, rt << 1, id);
  final(mi + 1, r, rt << 1 | 1, id);
  return;
}
int main() {
  n = read();
  q = read();
  scanf("%s", st + 1);
  for (int i = 1; i <= 26; i++) build(i, 1, n, 1);
  for (int p = 1; p <= q; p++) {
    x = read();
    y = read();
    op = read();
    if (op == 1) {
      int f = x;
      for (int i = 1; i <= 26; i++) {
        int len = Query(x, y, i, 1, n, 1);
        if (len == 0) continue;
        update(x, y, i, 0, 1, n, 1);
        update(f, f + len - 1, i, 1, 1, n, 1);
        f += len;
      }
    } else {
      int f = x;
      for (int i = 26; i >= 1; i--) {
        int len = Query(x, y, i, 1, n, 1);
        if (len == 0) continue;
        update(x, y, i, 0, 1, n, 1);
        update(f, f + len - 1, i, 1, 1, n, 1);
        f += len;
      }
    }
  }
  for (int i = 1; i <= 26; i++) final(1, n, 1, i);
  for (int i = 1; i <= n; i++) printf("%c", st[i]);
  printf("\n");
  return 0;
}