#include <bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
const int maxn = 100010;
struct soren {
  int left, right, num[30], lazy;
};
int a, b, c, d, e, i, ans[30];
soren tree[maxn * 4];
char s[maxn];
void update(int w) {
  int j, lc, rc;
  lc = w << 1;
  rc = w << 1 | 1;
  for (j = 1; j <= 26; j++) tree[w].num[j] = tree[lc].num[j] + tree[rc].num[j];
}
void pushdown(int w, int laz) {
  int j, t, lc, rc;
  lc = w << 1;
  rc = w << 1 | 1;
  tree[lc].lazy = tree[w].lazy;
  tree[rc].lazy = tree[w].lazy;
  tree[w].lazy = 0;
  for (j = 1; j <= 26; j++) {
    tree[lc].num[j] = 0;
    tree[rc].num[j] = 0;
  }
  if (laz == 1) {
    t = tree[lc].right - tree[lc].left + 1;
    for (j = 1; j <= 26 && t != 0; j++)
      if (t <= tree[w].num[j]) {
        tree[lc].num[j] = t;
        tree[w].num[j] = tree[w].num[j] - t;
        t = 0;
      } else {
        tree[lc].num[j] = tree[w].num[j];
        t = t - tree[w].num[j];
        tree[w].num[j] = 0;
      }
  } else {
    t = tree[lc].right - tree[lc].left + 1;
    for (j = 26; j >= 1 && t != 0; j--)
      if (t <= tree[w].num[j]) {
        tree[lc].num[j] = t;
        tree[w].num[j] = tree[w].num[j] - t;
        t = 0;
      } else {
        tree[lc].num[j] = tree[w].num[j];
        t = t - tree[w].num[j];
        tree[w].num[j] = 0;
      }
  }
  for (j = 1; j <= 26; j++) {
    tree[rc].num[j] = tree[w].num[j];
    tree[w].num[j] = tree[w].num[j] + tree[lc].num[j];
  }
}
void build(int w, int l, int r) {
  int lc, rc, mid;
  tree[w].left = l;
  tree[w].right = r;
  if (l == r) {
    tree[w].num[s[l - 1] - 'a' + 1]++;
    return;
  }
  lc = w << 1;
  rc = w << 1 | 1;
  mid = (l + r) / 2;
  build(lc, l, mid);
  build(rc, mid + 1, r);
  update(w);
}
void query(int w, int l, int r) {
  int j, lc, rc, mid;
  if (tree[w].left == l && tree[w].right == r) {
    for (j = 1; j <= 26; j++) {
      ans[j] = ans[j] + tree[w].num[j];
      tree[w].num[j] = 0;
    }
    return;
  }
  if (tree[w].lazy) pushdown(w, tree[w].lazy);
  lc = w << 1;
  rc = w << 1 | 1;
  mid = (tree[w].left + tree[w].right) / 2;
  if (mid >= r)
    query(lc, l, r);
  else if (mid < l)
    query(rc, l, r);
  else {
    query(lc, l, mid);
    query(rc, mid + 1, r);
  }
}
void change(int w, int l, int r) {
  int s, j, lc, rc, mid;
  if (tree[w].left == l && tree[w].right == r) {
    s = tree[w].right - tree[w].left + 1;
    for (j = 1; j <= 26 && s != 0; j++)
      if (ans[j] < s) {
        tree[w].num[j] = ans[j];
        s = s - ans[j];
        ans[j] = 0;
      } else {
        tree[w].num[j] = s;
        ans[j] = ans[j] - s;
        s = 0;
      }
    tree[w].lazy = 1;
    return;
  }
  if (tree[w].lazy) pushdown(w, tree[w].lazy);
  lc = w << 1;
  rc = w << 1 | 1;
  mid = (tree[w].left + tree[w].right) / 2;
  if (mid >= r)
    change(lc, l, r);
  else if (mid < l)
    change(rc, l, r);
  else {
    change(lc, l, mid);
    change(rc, mid + 1, r);
  }
  update(w);
}
void change2(int w, int l, int r) {
  int s, j, lc, rc, mid;
  if (tree[w].left == l && tree[w].right == r) {
    s = tree[w].right - tree[w].left + 1;
    for (j = 26; j >= 1 && s != 0; j--)
      if (ans[j] < s) {
        tree[w].num[j] = ans[j];
        s = s - ans[j];
        ans[j] = 0;
      } else {
        tree[w].num[j] = s;
        ans[j] = ans[j] - s;
        s = 0;
      }
    tree[w].lazy = 2;
    return;
  }
  if (tree[w].lazy) pushdown(w, tree[w].lazy);
  lc = w << 1;
  rc = w << 1 | 1;
  mid = (tree[w].left + tree[w].right) / 2;
  if (mid >= r)
    change2(lc, l, r);
  else if (mid < l)
    change2(rc, l, r);
  else {
    change2(lc, l, mid);
    change2(rc, mid + 1, r);
  }
  update(w);
}
void query2(int w) {
  int j, lc, rc;
  char anschar;
  if (tree[w].left == tree[w].right) {
    for (j = 1; j <= 26; j++)
      if (tree[w].num[j] != 0) {
        anschar = j + 'a' - 1;
        break;
      }
    printf("%c", anschar);
    return;
  }
  if (tree[w].lazy) pushdown(w, tree[w].lazy);
  lc = w << 1;
  rc = w << 1 | 1;
  query2(lc);
  query2(rc);
}
int main() {
  scanf("%d%d", &a, &b);
  scanf("%s", &s);
  build(1, 1, a);
  for (i = 1; i <= b; i++) {
    scanf("%d%d%d", &c, &d, &e);
    query(1, c, d);
    if (e == 1)
      change(1, c, d);
    else
      change2(1, c, d);
  }
  query2(1);
  return 0;
}

### Prompt

Create a solution in Cpp for 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>
#pragma GCC optimize(3)
using namespace std;
const int maxn = 100010;
struct soren {
  int left, right, num[30], lazy;
};
int a, b, c, d, e, i, ans[30];
soren tree[maxn * 4];
char s[maxn];
void update(int w) {
  int j, lc, rc;
  lc = w << 1;
  rc = w << 1 | 1;
  for (j = 1; j <= 26; j++) tree[w].num[j] = tree[lc].num[j] + tree[rc].num[j];
}
void pushdown(int w, int laz) {
  int j, t, lc, rc;
  lc = w << 1;
  rc = w << 1 | 1;
  tree[lc].lazy = tree[w].lazy;
  tree[rc].lazy = tree[w].lazy;
  tree[w].lazy = 0;
  for (j = 1; j <= 26; j++) {
    tree[lc].num[j] = 0;
    tree[rc].num[j] = 0;
  }
  if (laz == 1) {
    t = tree[lc].right - tree[lc].left + 1;
    for (j = 1; j <= 26 && t != 0; j++)
      if (t <= tree[w].num[j]) {
        tree[lc].num[j] = t;
        tree[w].num[j] = tree[w].num[j] - t;
        t = 0;
      } else {
        tree[lc].num[j] = tree[w].num[j];
        t = t - tree[w].num[j];
        tree[w].num[j] = 0;
      }
  } else {
    t = tree[lc].right - tree[lc].left + 1;
    for (j = 26; j >= 1 && t != 0; j--)
      if (t <= tree[w].num[j]) {
        tree[lc].num[j] = t;
        tree[w].num[j] = tree[w].num[j] - t;
        t = 0;
      } else {
        tree[lc].num[j] = tree[w].num[j];
        t = t - tree[w].num[j];
        tree[w].num[j] = 0;
      }
  }
  for (j = 1; j <= 26; j++) {
    tree[rc].num[j] = tree[w].num[j];
    tree[w].num[j] = tree[w].num[j] + tree[lc].num[j];
  }
}
void build(int w, int l, int r) {
  int lc, rc, mid;
  tree[w].left = l;
  tree[w].right = r;
  if (l == r) {
    tree[w].num[s[l - 1] - 'a' + 1]++;
    return;
  }
  lc = w << 1;
  rc = w << 1 | 1;
  mid = (l + r) / 2;
  build(lc, l, mid);
  build(rc, mid + 1, r);
  update(w);
}
void query(int w, int l, int r) {
  int j, lc, rc, mid;
  if (tree[w].left == l && tree[w].right == r) {
    for (j = 1; j <= 26; j++) {
      ans[j] = ans[j] + tree[w].num[j];
      tree[w].num[j] = 0;
    }
    return;
  }
  if (tree[w].lazy) pushdown(w, tree[w].lazy);
  lc = w << 1;
  rc = w << 1 | 1;
  mid = (tree[w].left + tree[w].right) / 2;
  if (mid >= r)
    query(lc, l, r);
  else if (mid < l)
    query(rc, l, r);
  else {
    query(lc, l, mid);
    query(rc, mid + 1, r);
  }
}
void change(int w, int l, int r) {
  int s, j, lc, rc, mid;
  if (tree[w].left == l && tree[w].right == r) {
    s = tree[w].right - tree[w].left + 1;
    for (j = 1; j <= 26 && s != 0; j++)
      if (ans[j] < s) {
        tree[w].num[j] = ans[j];
        s = s - ans[j];
        ans[j] = 0;
      } else {
        tree[w].num[j] = s;
        ans[j] = ans[j] - s;
        s = 0;
      }
    tree[w].lazy = 1;
    return;
  }
  if (tree[w].lazy) pushdown(w, tree[w].lazy);
  lc = w << 1;
  rc = w << 1 | 1;
  mid = (tree[w].left + tree[w].right) / 2;
  if (mid >= r)
    change(lc, l, r);
  else if (mid < l)
    change(rc, l, r);
  else {
    change(lc, l, mid);
    change(rc, mid + 1, r);
  }
  update(w);
}
void change2(int w, int l, int r) {
  int s, j, lc, rc, mid;
  if (tree[w].left == l && tree[w].right == r) {
    s = tree[w].right - tree[w].left + 1;
    for (j = 26; j >= 1 && s != 0; j--)
      if (ans[j] < s) {
        tree[w].num[j] = ans[j];
        s = s - ans[j];
        ans[j] = 0;
      } else {
        tree[w].num[j] = s;
        ans[j] = ans[j] - s;
        s = 0;
      }
    tree[w].lazy = 2;
    return;
  }
  if (tree[w].lazy) pushdown(w, tree[w].lazy);
  lc = w << 1;
  rc = w << 1 | 1;
  mid = (tree[w].left + tree[w].right) / 2;
  if (mid >= r)
    change2(lc, l, r);
  else if (mid < l)
    change2(rc, l, r);
  else {
    change2(lc, l, mid);
    change2(rc, mid + 1, r);
  }
  update(w);
}
void query2(int w) {
  int j, lc, rc;
  char anschar;
  if (tree[w].left == tree[w].right) {
    for (j = 1; j <= 26; j++)
      if (tree[w].num[j] != 0) {
        anschar = j + 'a' - 1;
        break;
      }
    printf("%c", anschar);
    return;
  }
  if (tree[w].lazy) pushdown(w, tree[w].lazy);
  lc = w << 1;
  rc = w << 1 | 1;
  query2(lc);
  query2(rc);
}
int main() {
  scanf("%d%d", &a, &b);
  scanf("%s", &s);
  build(1, 1, a);
  for (i = 1; i <= b; i++) {
    scanf("%d%d%d", &c, &d, &e);
    query(1, c, d);
    if (e == 1)
      change(1, c, d);
    else
      change2(1, c, d);
  }
  query2(1);
  return 0;
}

```