#include <bits/stdc++.h>
using namespace std;
__inline string next_line() {
  const int SIZE = 1100000;
  static char buf[SIZE + 1];
  static int p = SIZE;
  string res;
  int f = 1;
  while ((p < SIZE || (p = 0, buf[fread(buf, 1, SIZE, stdin)] = 0, buf[0])) &&
         (buf[p] != '\n' && (res += buf[p], f = 0, 1) || f))
    ++p;
  return res;
}
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1.0);
const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;
int sgn(double x) {
  if (fabs(x) < eps) return 0;
  if (x < 0)
    return -1;
  else
    return 1;
}
int n, m, d[26][MAXN << 2], lazy[26][MAXN << 2];
char str[MAXN];
void PushUp(int j, int rt) { d[j][rt] = d[j][rt << 1] + d[j][rt << 1 | 1]; }
void PushDown(int j, int rt, int m) {
  if (lazy[j][rt] == 1) {
    d[j][rt << 1] = (m - (m >> 1));
    d[j][rt << 1 | 1] = (m >> 1);
    lazy[j][rt << 1] = 1;
    lazy[j][rt << 1 | 1] = 1;
    lazy[j][rt] = 0;
  }
  if (lazy[j][rt] == -1) {
    d[j][rt << 1] = 0;
    d[j][rt << 1 | 1] = 0;
    lazy[j][rt << 1] = -1;
    lazy[j][rt << 1 | 1] = -1;
    lazy[j][rt] = 0;
  }
}
void Build(int l, int r, int rt) {
  if (l == r) {
    d[str[l] - 'a'][rt]++;
    return;
  }
  int mid = l + r >> 1;
  Build(l, mid, rt << 1);
  Build(mid + 1, r, rt << 1 | 1);
  for (int j = 0; j < 26; j++) PushUp(j, rt);
}
void UpDate(int j, int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    d[j][rt] = r - l + 1;
    lazy[j][rt] = 1;
    return;
  }
  PushDown(j, rt, r - l + 1);
  int mid = l + r >> 1;
  if (L <= mid) UpDate(j, L, R, l, mid, rt << 1);
  if (R > mid) UpDate(j, L, R, mid + 1, r, rt << 1 | 1);
  PushUp(j, rt);
}
int Query(int j, int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    int tmp = d[j][rt];
    d[j][rt] = 0;
    lazy[j][rt] = -1;
    return tmp;
  }
  PushDown(j, rt, r - l + 1);
  int mid = l + r >> 1, ret = 0;
  if (L <= mid) ret += Query(j, L, R, l, mid, rt << 1);
  if (R > mid) ret += Query(j, L, R, mid + 1, r, rt << 1 | 1);
  PushUp(j, rt);
  return ret;
}
int find(int pos, int l, int r, int rt) {
  if (l == r) {
    for (int j = 0; j < 26; j++) {
      if (d[j][rt]) return j;
    }
  }
  for (int j = 0; j < 26; j++) PushDown(j, rt, r - l + 1);
  int mid = l + r >> 1, ret;
  if (pos <= mid)
    ret = find(pos, l, mid, rt << 1);
  else
    ret = find(pos, mid + 1, r, rt << 1 | 1);
  for (int j = 0; j < 26; j++) PushUp(j, rt);
  return ret;
}
int main() {
  scanf("%d%d%s", &n, &m, str + 1);
  Build(1, n, 1);
  int op, l, r, b[26];
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &l, &r, &op);
    for (int j = 0; j < 26; j++) {
      b[j] = Query(j, l, r, 1, n, 1);
    }
    if (op == 1) {
      int pos = l;
      for (int j = 0; j < 26; j++) {
        if (b[j]) {
          UpDate(j, pos, pos + b[j] - 1, 1, n, 1);
          pos += b[j];
        }
      }
    } else {
      int pos = l;
      for (int j = 25; j >= 0; j--) {
        if (b[j]) {
          UpDate(j, pos, pos + b[j] - 1, 1, n, 1);
          pos += b[j];
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) printf("%c", find(i, 1, n, 1) + 'a');
  printf("\n");
}

### Prompt

Please formulate 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;
__inline string next_line() {
  const int SIZE = 1100000;
  static char buf[SIZE + 1];
  static int p = SIZE;
  string res;
  int f = 1;
  while ((p < SIZE || (p = 0, buf[fread(buf, 1, SIZE, stdin)] = 0, buf[0])) &&
         (buf[p] != '\n' && (res += buf[p], f = 0, 1) || f))
    ++p;
  return res;
}
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1.0);
const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;
int sgn(double x) {
  if (fabs(x) < eps) return 0;
  if (x < 0)
    return -1;
  else
    return 1;
}
int n, m, d[26][MAXN << 2], lazy[26][MAXN << 2];
char str[MAXN];
void PushUp(int j, int rt) { d[j][rt] = d[j][rt << 1] + d[j][rt << 1 | 1]; }
void PushDown(int j, int rt, int m) {
  if (lazy[j][rt] == 1) {
    d[j][rt << 1] = (m - (m >> 1));
    d[j][rt << 1 | 1] = (m >> 1);
    lazy[j][rt << 1] = 1;
    lazy[j][rt << 1 | 1] = 1;
    lazy[j][rt] = 0;
  }
  if (lazy[j][rt] == -1) {
    d[j][rt << 1] = 0;
    d[j][rt << 1 | 1] = 0;
    lazy[j][rt << 1] = -1;
    lazy[j][rt << 1 | 1] = -1;
    lazy[j][rt] = 0;
  }
}
void Build(int l, int r, int rt) {
  if (l == r) {
    d[str[l] - 'a'][rt]++;
    return;
  }
  int mid = l + r >> 1;
  Build(l, mid, rt << 1);
  Build(mid + 1, r, rt << 1 | 1);
  for (int j = 0; j < 26; j++) PushUp(j, rt);
}
void UpDate(int j, int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    d[j][rt] = r - l + 1;
    lazy[j][rt] = 1;
    return;
  }
  PushDown(j, rt, r - l + 1);
  int mid = l + r >> 1;
  if (L <= mid) UpDate(j, L, R, l, mid, rt << 1);
  if (R > mid) UpDate(j, L, R, mid + 1, r, rt << 1 | 1);
  PushUp(j, rt);
}
int Query(int j, int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    int tmp = d[j][rt];
    d[j][rt] = 0;
    lazy[j][rt] = -1;
    return tmp;
  }
  PushDown(j, rt, r - l + 1);
  int mid = l + r >> 1, ret = 0;
  if (L <= mid) ret += Query(j, L, R, l, mid, rt << 1);
  if (R > mid) ret += Query(j, L, R, mid + 1, r, rt << 1 | 1);
  PushUp(j, rt);
  return ret;
}
int find(int pos, int l, int r, int rt) {
  if (l == r) {
    for (int j = 0; j < 26; j++) {
      if (d[j][rt]) return j;
    }
  }
  for (int j = 0; j < 26; j++) PushDown(j, rt, r - l + 1);
  int mid = l + r >> 1, ret;
  if (pos <= mid)
    ret = find(pos, l, mid, rt << 1);
  else
    ret = find(pos, mid + 1, r, rt << 1 | 1);
  for (int j = 0; j < 26; j++) PushUp(j, rt);
  return ret;
}
int main() {
  scanf("%d%d%s", &n, &m, str + 1);
  Build(1, n, 1);
  int op, l, r, b[26];
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &l, &r, &op);
    for (int j = 0; j < 26; j++) {
      b[j] = Query(j, l, r, 1, n, 1);
    }
    if (op == 1) {
      int pos = l;
      for (int j = 0; j < 26; j++) {
        if (b[j]) {
          UpDate(j, pos, pos + b[j] - 1, 1, n, 1);
          pos += b[j];
        }
      }
    } else {
      int pos = l;
      for (int j = 25; j >= 0; j--) {
        if (b[j]) {
          UpDate(j, pos, pos + b[j] - 1, 1, n, 1);
          pos += b[j];
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) printf("%c", find(i, 1, n, 1) + 'a');
  printf("\n");
}

```