#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int sum[30][N << 2], b[N], add[30][N << 2];
int base[30], ans[N];
char a[N];
void pushup(int i, int rt) {
  sum[i][rt] = sum[i][rt << 1] + sum[i][rt << 1 | 1];
}
void build(int l, int r, int rt) {
  if (l == r) {
    for (int i = 1; i <= 26; i++) sum[i][rt] = ((i == b[l]) ? 1 : 0);
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  for (int i = 1; i <= 26; i++) add[i][rt] = -1, pushup(i, rt);
}
void pushdown(int type, int rt, int l, int r) {
  if (add[type][rt] != -1) {
    int mid = (l + r) >> 1;
    sum[type][rt << 1] = add[type][rt] * (mid - l + 1);
    sum[type][rt << 1 | 1] = add[type][rt] * (r - mid);
    add[type][rt << 1] = add[type][rt];
    add[type][rt << 1 | 1] = add[type][rt];
    add[type][rt] = -1;
  }
}
void update(int L, int R, int l, int r, int rt, int val, int type) {
  if (l >= L && r <= R) {
    sum[type][rt] = val * (r - l + 1);
    add[type][rt] = val;
    return;
  }
  pushdown(type, rt, l, r);
  int mid = (l + r) >> 1;
  if (L <= mid) update(L, R, l, mid, rt << 1, val, type);
  if (mid < R) update(L, R, mid + 1, r, rt << 1 | 1, val, type);
  pushup(type, rt);
}
int query(int L, int R, int l, int r, int rt, int type) {
  if (l >= L && r <= R) return sum[type][rt];
  pushdown(type, rt, l, r);
  int mid = (l + r) >> 1;
  int ans = 0;
  if (L <= mid) ans += query(L, R, l, mid, rt << 1, type);
  if (mid < R) ans += query(L, R, mid + 1, r, rt << 1 | 1, type);
  return ans;
}
void print(int n) {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= 26; j++) {
      if (query(i, i, 1, n, 1, j)) {
        ans[i] = j;
        break;
      }
    }
  for (int i = 1; i <= n; i++) printf("%c", (char)(ans[i] - 1) + 'a');
  puts("");
}
int main() {
  int n, q, l, r, k;
  scanf("%d%d", &n, &q);
  scanf("%s", a + 1);
  for (int i = 1; i <= n; i++) b[i] = a[i] - 'a' + 1;
  build(1, n, 1);
  while (q--) {
    scanf("%d%d%d", &l, &r, &k);
    for (int i = 1; i <= 26; i++)
      base[i] = query(l, r, 1, n, 1, i), base[i] += base[i - 1];
    for (int i = 1; i <= 26; i++) update(l, r, 1, n, 1, 0, i);
    int num = 0, len = r + l - 1;
    if (!k) {
      for (int i = 26; i >= 1; i--)
        if (base[i] != base[i - 1])
          update(r - base[i] + 1, r - base[i - 1], 1, n, 1, 1, i);
    } else {
      for (int i = 1; i <= 26; i++)
        if (base[i] != base[i - 1])
          update(l + base[i - 1], l + base[i] - 1, 1, n, 1, 1, i);
    }
  }
  print(n);
  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 = 1e5 + 5;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int sum[30][N << 2], b[N], add[30][N << 2];
int base[30], ans[N];
char a[N];
void pushup(int i, int rt) {
  sum[i][rt] = sum[i][rt << 1] + sum[i][rt << 1 | 1];
}
void build(int l, int r, int rt) {
  if (l == r) {
    for (int i = 1; i <= 26; i++) sum[i][rt] = ((i == b[l]) ? 1 : 0);
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  for (int i = 1; i <= 26; i++) add[i][rt] = -1, pushup(i, rt);
}
void pushdown(int type, int rt, int l, int r) {
  if (add[type][rt] != -1) {
    int mid = (l + r) >> 1;
    sum[type][rt << 1] = add[type][rt] * (mid - l + 1);
    sum[type][rt << 1 | 1] = add[type][rt] * (r - mid);
    add[type][rt << 1] = add[type][rt];
    add[type][rt << 1 | 1] = add[type][rt];
    add[type][rt] = -1;
  }
}
void update(int L, int R, int l, int r, int rt, int val, int type) {
  if (l >= L && r <= R) {
    sum[type][rt] = val * (r - l + 1);
    add[type][rt] = val;
    return;
  }
  pushdown(type, rt, l, r);
  int mid = (l + r) >> 1;
  if (L <= mid) update(L, R, l, mid, rt << 1, val, type);
  if (mid < R) update(L, R, mid + 1, r, rt << 1 | 1, val, type);
  pushup(type, rt);
}
int query(int L, int R, int l, int r, int rt, int type) {
  if (l >= L && r <= R) return sum[type][rt];
  pushdown(type, rt, l, r);
  int mid = (l + r) >> 1;
  int ans = 0;
  if (L <= mid) ans += query(L, R, l, mid, rt << 1, type);
  if (mid < R) ans += query(L, R, mid + 1, r, rt << 1 | 1, type);
  return ans;
}
void print(int n) {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= 26; j++) {
      if (query(i, i, 1, n, 1, j)) {
        ans[i] = j;
        break;
      }
    }
  for (int i = 1; i <= n; i++) printf("%c", (char)(ans[i] - 1) + 'a');
  puts("");
}
int main() {
  int n, q, l, r, k;
  scanf("%d%d", &n, &q);
  scanf("%s", a + 1);
  for (int i = 1; i <= n; i++) b[i] = a[i] - 'a' + 1;
  build(1, n, 1);
  while (q--) {
    scanf("%d%d%d", &l, &r, &k);
    for (int i = 1; i <= 26; i++)
      base[i] = query(l, r, 1, n, 1, i), base[i] += base[i - 1];
    for (int i = 1; i <= 26; i++) update(l, r, 1, n, 1, 0, i);
    int num = 0, len = r + l - 1;
    if (!k) {
      for (int i = 26; i >= 1; i--)
        if (base[i] != base[i - 1])
          update(r - base[i] + 1, r - base[i - 1], 1, n, 1, 1, i);
    } else {
      for (int i = 1; i <= 26; i++)
        if (base[i] != base[i - 1])
          update(l + base[i - 1], l + base[i] - 1, 1, n, 1, 1, i);
    }
  }
  print(n);
  return 0;
}

```