#include <bits/stdc++.h>
using namespace std;
const int N = 300050;
int n, m;
int tree[30][N << 2], lazy[30][N << 2];
int mo_ve[30];
string s;
char ans[N];
inline long long read() {
  long long re = 0, k = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') k = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    re = re * 10 + ch - '0';
    ch = getchar();
  }
  return re * k;
}
inline void push_up(int k, int root) {
  tree[k][root] = tree[k][root << 1] + tree[k][root << 1 | 1];
  return;
}
inline void push_down(int k, int l, int r, int root) {
  if (lazy[k][root] == -1) return;
  int mid = (l + r) >> 1;
  tree[k][root << 1] = (mid - l + 1) * lazy[k][root];
  tree[k][root << 1 | 1] = (r - mid) * lazy[k][root];
  lazy[k][root << 1] = lazy[k][root];
  lazy[k][root << 1 | 1] = lazy[k][root];
  lazy[k][root] = -1;
  return;
}
inline void build(int l, int r, int root) {
  if (l == r) {
    tree[s[l] - 'a' + 1][root] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, root << 1);
  build(mid + 1, r, root << 1 | 1);
  for (register int i = 1; i <= 26; i++) push_up(i, root);
  return;
}
inline void revise(int k, int l, int r, int root, int x, int y, int z) {
  if (x <= l && r <= y) {
    tree[k][root] = (r - l + 1) * z;
    lazy[k][root] = z;
    return;
  }
  int mid = (l + r) >> 1;
  push_down(k, l, r, root);
  if (x <= mid) revise(k, l, mid, root << 1, x, y, z);
  if (mid < y) revise(k, mid + 1, r, root << 1 | 1, x, y, z);
  push_up(k, root);
  return;
}
inline int query(int k, int l, int r, int root, int x, int y) {
  if (x <= l && r <= y) return tree[k][root];
  push_down(k, l, r, root);
  int mid = (l + r) >> 1, ssum = 0;
  if (x <= mid) ssum += query(k, l, mid, root << 1, x, y);
  if (mid < y) ssum += query(k, mid + 1, r, root << 1 | 1, x, y);
  return ssum;
}
int main() {
  memset(lazy, -1, sizeof(lazy));
  n = read(), m = read();
  cin >> s;
  s = ' ' + s;
  build(1, n, 1);
  for (register int i = 1; i <= m; i++) {
    int a = read(), b = read(), c = read();
    for (register int j = 1; j <= 26; j++) mo_ve[j] = query(j, 1, n, 1, a, b);
    for (register int j = 1; j <= 26; j++) revise(j, 1, n, 1, a, b, 0);
    int top = a;
    if (c) {
      for (register int j = 1; j <= 26; j++) {
        if (top > b) break;
        if (!mo_ve[j]) continue;
        revise(j, 1, n, 1, top, top + mo_ve[j] - 1, 1);
        top += mo_ve[j];
      }
    } else {
      for (register int j = 26; j > 0; j--) {
        if (top > b) break;
        if (!mo_ve[j]) continue;
        revise(j, 1, n, 1, top, top + mo_ve[j] - 1, 1);
        top += mo_ve[j];
      }
    }
  }
  for (register int i = 1; i <= n; i++) {
    for (register int j = 1; j <= 26; j++) {
      if (query(j, 1, n, 1, i, i)) {
        cout << (char)(j - 1 + 'a');
      }
    }
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve 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;
const int N = 300050;
int n, m;
int tree[30][N << 2], lazy[30][N << 2];
int mo_ve[30];
string s;
char ans[N];
inline long long read() {
  long long re = 0, k = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') k = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    re = re * 10 + ch - '0';
    ch = getchar();
  }
  return re * k;
}
inline void push_up(int k, int root) {
  tree[k][root] = tree[k][root << 1] + tree[k][root << 1 | 1];
  return;
}
inline void push_down(int k, int l, int r, int root) {
  if (lazy[k][root] == -1) return;
  int mid = (l + r) >> 1;
  tree[k][root << 1] = (mid - l + 1) * lazy[k][root];
  tree[k][root << 1 | 1] = (r - mid) * lazy[k][root];
  lazy[k][root << 1] = lazy[k][root];
  lazy[k][root << 1 | 1] = lazy[k][root];
  lazy[k][root] = -1;
  return;
}
inline void build(int l, int r, int root) {
  if (l == r) {
    tree[s[l] - 'a' + 1][root] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, root << 1);
  build(mid + 1, r, root << 1 | 1);
  for (register int i = 1; i <= 26; i++) push_up(i, root);
  return;
}
inline void revise(int k, int l, int r, int root, int x, int y, int z) {
  if (x <= l && r <= y) {
    tree[k][root] = (r - l + 1) * z;
    lazy[k][root] = z;
    return;
  }
  int mid = (l + r) >> 1;
  push_down(k, l, r, root);
  if (x <= mid) revise(k, l, mid, root << 1, x, y, z);
  if (mid < y) revise(k, mid + 1, r, root << 1 | 1, x, y, z);
  push_up(k, root);
  return;
}
inline int query(int k, int l, int r, int root, int x, int y) {
  if (x <= l && r <= y) return tree[k][root];
  push_down(k, l, r, root);
  int mid = (l + r) >> 1, ssum = 0;
  if (x <= mid) ssum += query(k, l, mid, root << 1, x, y);
  if (mid < y) ssum += query(k, mid + 1, r, root << 1 | 1, x, y);
  return ssum;
}
int main() {
  memset(lazy, -1, sizeof(lazy));
  n = read(), m = read();
  cin >> s;
  s = ' ' + s;
  build(1, n, 1);
  for (register int i = 1; i <= m; i++) {
    int a = read(), b = read(), c = read();
    for (register int j = 1; j <= 26; j++) mo_ve[j] = query(j, 1, n, 1, a, b);
    for (register int j = 1; j <= 26; j++) revise(j, 1, n, 1, a, b, 0);
    int top = a;
    if (c) {
      for (register int j = 1; j <= 26; j++) {
        if (top > b) break;
        if (!mo_ve[j]) continue;
        revise(j, 1, n, 1, top, top + mo_ve[j] - 1, 1);
        top += mo_ve[j];
      }
    } else {
      for (register int j = 26; j > 0; j--) {
        if (top > b) break;
        if (!mo_ve[j]) continue;
        revise(j, 1, n, 1, top, top + mo_ve[j] - 1, 1);
        top += mo_ve[j];
      }
    }
  }
  for (register int i = 1; i <= n; i++) {
    for (register int j = 1; j <= 26; j++) {
      if (query(j, 1, n, 1, i, i)) {
        cout << (char)(j - 1 + 'a');
      }
    }
  }
  return 0;
}

```