#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, m;
int cnt[MAXN * 4][26], tag[MAXN * 4], res[26];
char s[MAXN];
inline void push_up(int p) {
  for (int i = 0; i < 26; i++) cnt[p][i] = cnt[p << 1][i] + cnt[p << 1 | 1][i];
}
inline void push_tag(int p, int l, int r, int v) {
  tag[p] = v;
  for (int i = 0; i < 26; i++) cnt[p][i] = 0;
  cnt[p][v] = r - l + 1;
}
inline void push_down(int p, int l, int r) {
  if (tag[p] < 26) {
    int mid = (l + r) >> 1;
    push_tag(p << 1, l, mid, tag[p]);
    push_tag(p << 1 | 1, mid + 1, r, tag[p]);
    tag[p] = 26;
  }
}
void build(int p, int l, int r) {
  tag[p] = 26;
  if (l == r) return cnt[p][s[l] - 'a']++, void();
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
  push_up(p);
}
void query(int p, int l, int r, int ql, int qr, int *res) {
  if (ql <= l && r <= qr) {
    for (int i = 0; i < 26; i++) res[i] += cnt[p][i];
    return;
  }
  int mid = (l + r) >> 1;
  push_down(p, l, r);
  if (ql <= mid) query(p << 1, l, mid, ql, qr, res);
  if (qr > mid) query(p << 1 | 1, mid + 1, r, ql, qr, res);
}
void upd(int p, int l, int r, int ql, int qr, int v) {
  if (ql > qr) return;
  if (ql <= l && r <= qr) return push_tag(p, l, r, v), void();
  int mid = (l + r) >> 1;
  push_down(p, l, r);
  if (ql <= mid) upd(p << 1, l, mid, ql, qr, v);
  if (qr > mid) upd(p << 1 | 1, mid + 1, r, ql, qr, v);
  push_up(p);
}
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    (x *= 10) += ch - '0';
    ch = getchar();
  }
  return x * f;
}
void get_ans(int p, int l, int r) {
  if (l == r) {
    for (int i = 0; i < 26; i++)
      if (cnt[p][i] == 1) return putchar('a' + i), void();
  }
  int mid = (l + r) >> 1;
  push_down(p, l, r);
  get_ans(p << 1, l, mid);
  get_ans(p << 1 | 1, mid + 1, r);
}
int main() {
  n = read(), m = read();
  scanf("%s", s + 1);
  build(1, 1, n);
  for (int i = 1, l, r, typ, p; i <= m; i++) {
    l = read(), r = read(), typ = read();
    memset(res, 0, sizeof(res));
    query(1, 1, n, l, r, res);
    p = l;
    for (int i = (typ ? 0 : 25); i != (typ ? 26 : -1); i += (typ ? 1 : -1))
      upd(1, 1, n, p, p + res[i] - 1, i), p += res[i];
  }
  get_ans(1, 1, n);
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, m;
int cnt[MAXN * 4][26], tag[MAXN * 4], res[26];
char s[MAXN];
inline void push_up(int p) {
  for (int i = 0; i < 26; i++) cnt[p][i] = cnt[p << 1][i] + cnt[p << 1 | 1][i];
}
inline void push_tag(int p, int l, int r, int v) {
  tag[p] = v;
  for (int i = 0; i < 26; i++) cnt[p][i] = 0;
  cnt[p][v] = r - l + 1;
}
inline void push_down(int p, int l, int r) {
  if (tag[p] < 26) {
    int mid = (l + r) >> 1;
    push_tag(p << 1, l, mid, tag[p]);
    push_tag(p << 1 | 1, mid + 1, r, tag[p]);
    tag[p] = 26;
  }
}
void build(int p, int l, int r) {
  tag[p] = 26;
  if (l == r) return cnt[p][s[l] - 'a']++, void();
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
  push_up(p);
}
void query(int p, int l, int r, int ql, int qr, int *res) {
  if (ql <= l && r <= qr) {
    for (int i = 0; i < 26; i++) res[i] += cnt[p][i];
    return;
  }
  int mid = (l + r) >> 1;
  push_down(p, l, r);
  if (ql <= mid) query(p << 1, l, mid, ql, qr, res);
  if (qr > mid) query(p << 1 | 1, mid + 1, r, ql, qr, res);
}
void upd(int p, int l, int r, int ql, int qr, int v) {
  if (ql > qr) return;
  if (ql <= l && r <= qr) return push_tag(p, l, r, v), void();
  int mid = (l + r) >> 1;
  push_down(p, l, r);
  if (ql <= mid) upd(p << 1, l, mid, ql, qr, v);
  if (qr > mid) upd(p << 1 | 1, mid + 1, r, ql, qr, v);
  push_up(p);
}
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    (x *= 10) += ch - '0';
    ch = getchar();
  }
  return x * f;
}
void get_ans(int p, int l, int r) {
  if (l == r) {
    for (int i = 0; i < 26; i++)
      if (cnt[p][i] == 1) return putchar('a' + i), void();
  }
  int mid = (l + r) >> 1;
  push_down(p, l, r);
  get_ans(p << 1, l, mid);
  get_ans(p << 1 | 1, mid + 1, r);
}
int main() {
  n = read(), m = read();
  scanf("%s", s + 1);
  build(1, 1, n);
  for (int i = 1, l, r, typ, p; i <= m; i++) {
    l = read(), r = read(), typ = read();
    memset(res, 0, sizeof(res));
    query(1, 1, n, l, r, res);
    p = l;
    for (int i = (typ ? 0 : 25); i != (typ ? 26 : -1); i += (typ ? 1 : -1))
      upd(1, 1, n, p, p + res[i] - 1, i), p += res[i];
  }
  get_ans(1, 1, n);
  return 0;
}

```