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>
int n, q, a[100010][30], sum[400010][30], tag[400010][30], cnt[30];
char s[100010];
inline void pushup(int i, int tp) {
  sum[i][tp] = sum[i << 1][tp] + sum[i << 1 | 1][tp];
}
void build(int i, int l, int r, int tp) {
  tag[i][tp] = -1;
  if (l == r) {
    if (a[l][tp]) sum[i][tp] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(i << 1, l, mid, tp), build(i << 1 | 1, mid + 1, r, tp);
  pushup(i, tp);
}
inline void upd(int i, int l, int r, int tp, int v) {
  tag[i][tp] = v;
  sum[i][tp] = (r - l + 1) * v;
}
inline void pushdown(int i, int l, int r, int mid, int tp) {
  if (tag[i][tp] != -1) {
    upd(i << 1, l, mid, tp, tag[i][tp]);
    upd(i << 1 | 1, mid + 1, r, tp, tag[i][tp]);
    tag[i][tp] = -1;
  }
}
int query(int i, int l, int r, int x, int y, int tp) {
  if (l >= x && r <= y) return sum[i][tp];
  int mid = (l + r) >> 1, sum = 0;
  pushdown(i, l, r, mid, tp);
  if (x <= mid) sum += query(i << 1, l, mid, x, y, tp);
  if (y > mid) sum += query(i << 1 | 1, mid + 1, r, x, y, tp);
  return sum;
}
void modify(int i, int l, int r, int x, int y, int tp, int v) {
  if (l >= x && r <= y) {
    upd(i, l, r, tp, v);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(i, l, r, mid, tp);
  if (x <= mid) modify(i << 1, l, mid, x, y, tp, v);
  if (y > mid) modify(i << 1 | 1, mid + 1, r, x, y, tp, v);
  pushup(i, tp);
}
int main() {
  scanf("%d%d%s", &n, &q, s + 1);
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < 26; j++)
      if (j == s[i] - 'a') a[i][j] = 1;
  for (int j = 0; j < 26; j++) build(1, 1, n, j);
  for (int i = 1, op, l, r, now; i <= q; i++) {
    scanf("%d%d%d", &l, &r, &op);
    for (int j = 0; j < 26; j++) cnt[j] = query(1, 1, n, l, r, j);
    for (int j = 0; j < 26; j++) modify(1, 1, n, l, r, j, 0);
    if (op == 1) {
      now = l;
      for (int j = 0, las; j < 26; j++) {
        las = now, now += cnt[j];
        if (las < now) modify(1, 1, n, las, now - 1, j, 1);
      }
    } else {
      now = l;
      for (int j = 25, las; j >= 0; j--) {
        las = now, now += cnt[j];
        if (las < now) modify(1, 1, n, las, now - 1, j, 1);
      }
    }
  }
  for (int i = 1, now; i <= n; i++)
    for (int j = 0; j < 26; j++)
      if (query(1, 1, n, i, i, j) == 1) {
        putchar(j + 'a');
        break;
      }
  puts("");
  return 0;
}