#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 30;
int n, q;
int cnt[M];
char ch[N];
struct ST {
  int lazy[N << 2], num[N << 2];
  void init() {
    memset(lazy, -1, sizeof(lazy));
    memset(num, 0, sizeof(num));
  }
  void pushDown(int l, int r, int rt) {
    int mid = (l + r) >> 1;
    if (lazy[rt] == 0) {
      num[rt << 1] = num[rt << 1 | 1] = 0;
      lazy[rt << 1] = lazy[rt << 1 | 1] = 0;
    } else {
      num[rt << 1] = mid - l + 1;
      num[rt << 1 | 1] = r - mid;
      lazy[rt << 1] = lazy[rt << 1 | 1] = 1;
    }
    lazy[rt] = -1;
  }
  void pushUp(int l, int r, int rt) {
    num[rt] = num[rt << 1] + num[rt << 1 | 1];
  }
  void get(int l, int r, int rt, char c) {
    if (l == r) {
      ch[l] = c;
      return;
    }
    if (lazy[rt] != -1) pushDown(l, r, rt);
    int mid = (l + r) >> 1;
    if (num[rt << 1] != 0) get(l, mid, rt << 1, c);
    if (num[rt << 1 | 1] != 0) get(mid + 1, r, rt << 1 | 1, c);
    pushUp(l, r, rt);
  }
  int query(int l, int r, int rt, int x, int y) {
    if (x <= l && y >= r) {
      int ret = num[rt];
      num[rt] = 0;
      lazy[rt] = 0;
      return ret;
    }
    if (lazy[rt] != -1) pushDown(l, r, rt);
    int ret = 0;
    int mid = (l + r) >> 1;
    if (x <= mid && num[rt << 1] != 0) ret += query(l, mid, rt << 1, x, y);
    if (y > mid && num[rt << 1 | 1] != 0)
      ret += query(mid + 1, r, rt << 1 | 1, x, y);
    pushUp(l, r, rt);
    return ret;
  }
  void update(int l, int r, int rt, int x, int y) {
    if (x <= l && y >= r) {
      num[rt] = (r - l + 1);
      lazy[rt] = 1;
      return;
    }
    if (lazy[rt] != -1) pushDown(l, r, rt);
    int mid = (l + r) >> 1;
    if (x <= mid) update(l, mid, rt << 1, x, y);
    if (y > mid) update(mid + 1, r, rt << 1 | 1, x, y);
    pushUp(l, r, rt);
  }
} st[26];
int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", ch + 1);
  for (int i = 0; i < 26; i++) st[i].init();
  for (int i = 1; i <= n; i++) {
    int idx = ch[i] - 'a';
    st[idx].update(1, n, 1, i, i);
  }
  for (int i = 0; i < q; i++) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    for (int j = 0; j < 26; j++) cnt[j] = st[j].query(1, n, 1, l, r);
    if (k) {
      int tl = l;
      for (int j = 0; j < 26; j++) {
        if (cnt[j] == 0) continue;
        st[j].update(1, n, 1, tl, tl + cnt[j] - 1);
        tl = tl + cnt[j];
      }
    } else {
      int tl = l;
      for (int j = 25; j >= 0; j--) {
        if (cnt[j] == 0) continue;
        st[j].update(1, n, 1, tl, tl + cnt[j] - 1);
        tl = tl + cnt[j];
      }
    }
  }
  for (int i = 0; i < 26; i++) st[i].get(1, n, 1, 'a' + i);
  puts(ch + 1);
  return 0;
}

### Prompt

Generate 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;
const int N = 1e5 + 5;
const int M = 30;
int n, q;
int cnt[M];
char ch[N];
struct ST {
  int lazy[N << 2], num[N << 2];
  void init() {
    memset(lazy, -1, sizeof(lazy));
    memset(num, 0, sizeof(num));
  }
  void pushDown(int l, int r, int rt) {
    int mid = (l + r) >> 1;
    if (lazy[rt] == 0) {
      num[rt << 1] = num[rt << 1 | 1] = 0;
      lazy[rt << 1] = lazy[rt << 1 | 1] = 0;
    } else {
      num[rt << 1] = mid - l + 1;
      num[rt << 1 | 1] = r - mid;
      lazy[rt << 1] = lazy[rt << 1 | 1] = 1;
    }
    lazy[rt] = -1;
  }
  void pushUp(int l, int r, int rt) {
    num[rt] = num[rt << 1] + num[rt << 1 | 1];
  }
  void get(int l, int r, int rt, char c) {
    if (l == r) {
      ch[l] = c;
      return;
    }
    if (lazy[rt] != -1) pushDown(l, r, rt);
    int mid = (l + r) >> 1;
    if (num[rt << 1] != 0) get(l, mid, rt << 1, c);
    if (num[rt << 1 | 1] != 0) get(mid + 1, r, rt << 1 | 1, c);
    pushUp(l, r, rt);
  }
  int query(int l, int r, int rt, int x, int y) {
    if (x <= l && y >= r) {
      int ret = num[rt];
      num[rt] = 0;
      lazy[rt] = 0;
      return ret;
    }
    if (lazy[rt] != -1) pushDown(l, r, rt);
    int ret = 0;
    int mid = (l + r) >> 1;
    if (x <= mid && num[rt << 1] != 0) ret += query(l, mid, rt << 1, x, y);
    if (y > mid && num[rt << 1 | 1] != 0)
      ret += query(mid + 1, r, rt << 1 | 1, x, y);
    pushUp(l, r, rt);
    return ret;
  }
  void update(int l, int r, int rt, int x, int y) {
    if (x <= l && y >= r) {
      num[rt] = (r - l + 1);
      lazy[rt] = 1;
      return;
    }
    if (lazy[rt] != -1) pushDown(l, r, rt);
    int mid = (l + r) >> 1;
    if (x <= mid) update(l, mid, rt << 1, x, y);
    if (y > mid) update(mid + 1, r, rt << 1 | 1, x, y);
    pushUp(l, r, rt);
  }
} st[26];
int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", ch + 1);
  for (int i = 0; i < 26; i++) st[i].init();
  for (int i = 1; i <= n; i++) {
    int idx = ch[i] - 'a';
    st[idx].update(1, n, 1, i, i);
  }
  for (int i = 0; i < q; i++) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    for (int j = 0; j < 26; j++) cnt[j] = st[j].query(1, n, 1, l, r);
    if (k) {
      int tl = l;
      for (int j = 0; j < 26; j++) {
        if (cnt[j] == 0) continue;
        st[j].update(1, n, 1, tl, tl + cnt[j] - 1);
        tl = tl + cnt[j];
      }
    } else {
      int tl = l;
      for (int j = 25; j >= 0; j--) {
        if (cnt[j] == 0) continue;
        st[j].update(1, n, 1, tl, tl + cnt[j] - 1);
        tl = tl + cnt[j];
      }
    }
  }
  for (int i = 0; i < 26; i++) st[i].get(1, n, 1, 'a' + i);
  puts(ch + 1);
  return 0;
}

```