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 N = 100010;
int n, q;
char s[N];
int t[26][4 * N];
int c[26][4 * N];
int d[26];
void pushDown(int id, int p, int l, int r, int m) {
  if (c[id][p] == 0) {
    t[id][p << 1] = 0;
    t[id][p << 1 | 1] = 0;
    c[id][p << 1] = 0;
    c[id][p << 1 | 1] = 0;
    c[id][p] = -1;
  } else if (c[id][p] == 1) {
    t[id][p << 1] = m - l + 1;
    t[id][p << 1 | 1] = r - m;
    c[id][p << 1] = 1;
    c[id][p << 1 | 1] = 1;
    c[id][p] = -1;
  }
}
void update(int id, int p, int l, int r, int u, int v, int add) {
  if (v < l || r < u) return;
  if (u <= l && r <= v) {
    t[id][p] = (r - l + 1) * add;
    c[id][p] = add;
    return;
  }
  int m = (l + r) >> 1;
  pushDown(id, p, l, r, m);
  update(id, p << 1, l, m, u, v, add);
  update(id, p << 1 | 1, m + 1, r, u, v, add);
  t[id][p] = t[id][p << 1] + t[id][p << 1 | 1];
}
int getSum(int id, int p, int l, int r, int u, int v) {
  if (v < l || r < u) return 0;
  if (u <= l && r <= v) return t[id][p];
  int m = (l + r) >> 1;
  pushDown(id, p, l, r, m);
  int t1 = getSum(id, p << 1, l, m, u, v);
  int t2 = getSum(id, p << 1 | 1, m + 1, r, u, v);
  return t1 + t2;
}
int main() {
  scanf("%d %d\n", &n, &q);
  scanf("%s\n", s);
  memset(t, 0, sizeof t);
  memset(c, 0xff, sizeof c);
  for (int i = 0; i < n; ++i) update(s[i] - 'a', 1, 1, n, i + 1, i + 1, 1);
  while (q--) {
    int u, v, type;
    scanf("%d %d %d\n", &u, &v, &type);
    for (int i = 0; i < 26; ++i) d[i] = getSum(i, 1, 1, n, u, v);
    for (int i = 0; i < 26; ++i) update(i, 1, 1, n, u, v, 0);
    if (type == 1) {
      int p = u;
      for (int i = 0; i < 26; ++i)
        if (d[i]) {
          update(i, 1, 1, n, p, p + d[i] - 1, 1);
          p += d[i];
        }
    } else {
      int p = u;
      for (int i = 25; i >= 0; --i)
        if (d[i]) {
          update(i, 1, 1, n, p, p + d[i] - 1, 1);
          p += d[i];
        }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 26; ++j) {
      int p = getSum(j, 1, 1, n, i, i);
      if (p) {
        printf("%c", 'a' + j);
        break;
      }
    }
  }
  printf("\n");
  return 0;
}