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;
template <class T>
void read(T &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  x *= f;
}
const int MAXN = 110000;
int cntv[MAXN << 2][30], setv[MAXN << 2], num[30];
int n, m, ql, qr, qv;
char s[MAXN];
void Pushdown(int u, int l, int r) {
  if (!setv[u]) return;
  int mid = l + r >> 1;
  setv[u << 1] = setv[u << 1 | 1] = setv[u];
  memset(cntv[u << 1], 0, sizeof(cntv[u << 1]));
  memset(cntv[u << 1 | 1], 0, sizeof(cntv[u << 1 | 1]));
  cntv[u << 1][setv[u]] = mid - l;
  cntv[u << 1 | 1][setv[u]] = r - mid;
  setv[u] = 0;
}
void Pushup(int u, int l, int r) {
  for (int i = 1; i <= 26; ++i)
    cntv[u][i] = cntv[u << 1][i] + cntv[u << 1 | 1][i];
}
void Update(int u, int l, int r) {
  if (ql <= l && r <= qr) {
    memset(cntv[u], 0, sizeof(cntv[u]));
    setv[u] = qv;
    cntv[u][qv] = r - l;
  } else {
    int mid = l + r >> 1;
    Pushdown(u, l, r);
    if (ql < mid) Update(u << 1, l, mid);
    if (qr > mid) Update(u << 1 | 1, mid, r);
    Pushup(u, l, r);
  }
}
void Query(int u, int l, int r) {
  if (ql <= l && r <= qr) {
    for (int i = 1; i <= 26; ++i) num[i] += cntv[u][i];
  } else {
    int mid = l + r >> 1;
    Pushdown(u, l, r);
    if (ql < mid) Query(u << 1, l, mid);
    if (qr > mid) Query(u << 1 | 1, mid, r);
  }
}
int main() {
  read(n), read(m);
  scanf("%s", s + 1);
  for (int i = 1; i <= n; ++i) {
    ql = qr = i;
    qr++;
    qv = s[i] - 'a' + 1;
    Update(1, 1, n + 1);
  }
  while (m--) {
    memset(num, 0, sizeof(num));
    int op;
    read(ql), read(qr), read(op);
    qr++;
    Query(1, 1, n + 1);
    if (op == 1) {
      qr = ql;
      for (int i = 1; i <= 26; ++i) {
        if (num[i]) {
          ql = qr;
          qr = ql + num[i];
          qv = i;
          Update(1, 1, n + 1);
        }
      }
    } else {
      qr = ql;
      for (int i = 26; i >= 1; --i) {
        if (num[i]) {
          ql = qr;
          qr = ql + num[i];
          qv = i;
          Update(1, 1, n + 1);
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    memset(num, 0, sizeof(num));
    ql = qr = i;
    qr++;
    Query(1, 1, n + 1);
    for (int j = 1; j <= 26; ++j)
      if (num[j]) printf("%c", j - 1 + 'a');
  }
  return 0;
}