#include <bits/stdc++.h>
using namespace std;
int tree[1100000], ans[31][110000];
int a[110000], b[110000];
char s[110000];
int n, m, q;
struct questions {
  int op, l, r;
} ques[110000];
void pushdown(int now, int l, int r) {
  int mid = (l + r) >> 1;
  if (tree[now] == r - l + 1) {
    tree[((now) << 1)] = mid - l + 1;
    tree[((now) << 1 | 1)] = r - mid;
  }
  if (!tree[now]) {
    tree[((now) << 1)] = 0;
    tree[((now) << 1 | 1)] = 0;
  }
}
void update(int now) {
  tree[now] = tree[((now) << 1)] + tree[((now) << 1 | 1)];
}
void buildtree(int now, int l, int r) {
  if (l > r) return;
  if (l == r) {
    tree[now] = b[l];
    return;
  }
  int mid = (l + r) >> 1;
  buildtree(((now) << 1), l, mid);
  buildtree(((now) << 1 | 1), mid + 1, r);
  update(now);
}
void change(int now, int l, int r, int x, int y, int v) {
  if (l > r || x > y) return;
  if (x == l && r == y) {
    tree[now] = v * (r - l + 1);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(now, l, r);
  if (y <= mid)
    change(((now) << 1), l, mid, x, y, v);
  else if (x > mid)
    change(((now) << 1 | 1), mid + 1, r, x, y, v);
  else {
    change(((now) << 1), l, mid, x, mid, v);
    change(((now) << 1 | 1), mid + 1, r, mid + 1, y, v);
  }
  update(now);
  pushdown(now, l, r);
}
int query(int now, int l, int r, int x, int y) {
  if (l > r || x > y) return 0;
  if (x == l && r == y) return tree[now];
  int mid = (l + r) >> 1;
  pushdown(now, l, r);
  if (y <= mid)
    return query(((now) << 1), l, mid, x, y);
  else if (x > mid)
    return query(((now) << 1 | 1), mid + 1, r, x, y);
  else
    return query(((now) << 1), l, mid, x, mid) +
           query(((now) << 1 | 1), mid + 1, r, mid + 1, y);
}
void work() {
  for (int now = 1; now <= 26; now++) {
    for (int i = 1; i <= n; i++) b[i] = (a[i] >= now);
    buildtree(1, 1, n);
    for (int i = 1; i <= m; i++) {
      int k = query(1, 1, n, ques[i].l, ques[i].r);
      if (!ques[i].op) {
        change(1, 1, n, ques[i].l, ques[i].l + k - 1, 1);
        change(1, 1, n, ques[i].l + k, ques[i].r, 0);
      } else {
        k = ques[i].r - ques[i].l + 1 - k;
        change(1, 1, n, ques[i].l, ques[i].l + k - 1, 0);
        change(1, 1, n, ques[i].l + k, ques[i].r, 1);
      }
    }
    for (int i = 1; i <= n; i++) ans[now][i] = query(1, 1, n, i, i);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  scanf("%s", s + 1);
  for (int i = 1; i <= n; i++) a[i] = s[i] - 'a' + 1;
  for (int i = 1; i <= m; i++)
    scanf("%d%d%d", &ques[i].l, &ques[i].r, &ques[i].op);
  work();
  for (int i = 1; i <= n; i++)
    for (int now = 26; now >= 1; now--)
      if (ans[now][i]) {
        putchar(now + 'a' - 1);
        break;
      }
  return 0;
}

### Prompt

Your task is to create a CPP solution to the following 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>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int tree[1100000], ans[31][110000];
int a[110000], b[110000];
char s[110000];
int n, m, q;
struct questions {
  int op, l, r;
} ques[110000];
void pushdown(int now, int l, int r) {
  int mid = (l + r) >> 1;
  if (tree[now] == r - l + 1) {
    tree[((now) << 1)] = mid - l + 1;
    tree[((now) << 1 | 1)] = r - mid;
  }
  if (!tree[now]) {
    tree[((now) << 1)] = 0;
    tree[((now) << 1 | 1)] = 0;
  }
}
void update(int now) {
  tree[now] = tree[((now) << 1)] + tree[((now) << 1 | 1)];
}
void buildtree(int now, int l, int r) {
  if (l > r) return;
  if (l == r) {
    tree[now] = b[l];
    return;
  }
  int mid = (l + r) >> 1;
  buildtree(((now) << 1), l, mid);
  buildtree(((now) << 1 | 1), mid + 1, r);
  update(now);
}
void change(int now, int l, int r, int x, int y, int v) {
  if (l > r || x > y) return;
  if (x == l && r == y) {
    tree[now] = v * (r - l + 1);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(now, l, r);
  if (y <= mid)
    change(((now) << 1), l, mid, x, y, v);
  else if (x > mid)
    change(((now) << 1 | 1), mid + 1, r, x, y, v);
  else {
    change(((now) << 1), l, mid, x, mid, v);
    change(((now) << 1 | 1), mid + 1, r, mid + 1, y, v);
  }
  update(now);
  pushdown(now, l, r);
}
int query(int now, int l, int r, int x, int y) {
  if (l > r || x > y) return 0;
  if (x == l && r == y) return tree[now];
  int mid = (l + r) >> 1;
  pushdown(now, l, r);
  if (y <= mid)
    return query(((now) << 1), l, mid, x, y);
  else if (x > mid)
    return query(((now) << 1 | 1), mid + 1, r, x, y);
  else
    return query(((now) << 1), l, mid, x, mid) +
           query(((now) << 1 | 1), mid + 1, r, mid + 1, y);
}
void work() {
  for (int now = 1; now <= 26; now++) {
    for (int i = 1; i <= n; i++) b[i] = (a[i] >= now);
    buildtree(1, 1, n);
    for (int i = 1; i <= m; i++) {
      int k = query(1, 1, n, ques[i].l, ques[i].r);
      if (!ques[i].op) {
        change(1, 1, n, ques[i].l, ques[i].l + k - 1, 1);
        change(1, 1, n, ques[i].l + k, ques[i].r, 0);
      } else {
        k = ques[i].r - ques[i].l + 1 - k;
        change(1, 1, n, ques[i].l, ques[i].l + k - 1, 0);
        change(1, 1, n, ques[i].l + k, ques[i].r, 1);
      }
    }
    for (int i = 1; i <= n; i++) ans[now][i] = query(1, 1, n, i, i);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  scanf("%s", s + 1);
  for (int i = 1; i <= n; i++) a[i] = s[i] - 'a' + 1;
  for (int i = 1; i <= m; i++)
    scanf("%d%d%d", &ques[i].l, &ques[i].r, &ques[i].op);
  work();
  for (int i = 1; i <= n; i++)
    for (int now = 26; now >= 1; now--)
      if (ans[now][i]) {
        putchar(now + 'a' - 1);
        break;
      }
  return 0;
}

```