#include <bits/stdc++.h>
using namespace std;
char str[100005];
struct data {
  int cnt[27];
  int lazy;
  data() {
    memset(cnt, 0, sizeof(cnt));
    lazy = 0;
  }
  void clear() {
    lazy = 0;
    memset(cnt, 0, sizeof(cnt));
  }
  void add(data a) {
    for (int i = 1; i <= 26; i++) cnt[i] += a.cnt[i];
  }
};
data tree[6 * 100005];
void push_down(int n, int b, int e) {
  if (tree[n].lazy > 0) {
    int l = n * 2, r = l + 1, mid = (b + e) / 2;
    tree[l].clear();
    int x = tree[n].lazy;
    tree[l].lazy = x;
    int totall = mid - b + 1;
    tree[l].cnt[x] = totall;
    tree[r].clear();
    int totalr = e - mid;
    tree[r].lazy = x;
    tree[r].cnt[x] = totalr;
    tree[n].lazy = 0;
  }
  tree[n].lazy = 0;
}
void push_up(int n, int l, int r) {
  tree[n].clear();
  tree[n].add(tree[l]);
  tree[n].add(tree[r]);
}
void update(int n, int b, int e, int i, int j, int val) {
  if (b > j || e < i) return;
  if (b >= i && e <= j) {
    tree[n].clear();
    tree[n].lazy = val;
    int total = e - b + 1;
    tree[n].cnt[val] = total;
    return;
  }
  int l = n * 2, r = l + 1, mid = (b + e) / 2;
  push_down(n, b, e);
  update(l, b, mid, i, j, val);
  update(r, mid + 1, e, i, j, val);
  push_up(n, l, r);
}
data query(int n, int b, int e, int i, int j) {
  if (b > j || e < i) return tree[0];
  if (b >= i && e <= j) {
    return tree[n];
  }
  int l = n * 2, r = l + 1, mid = (b + e) / 2;
  push_down(n, b, e);
  data p = query(l, b, mid, i, j);
  data q = query(r, mid + 1, e, i, j);
  p.add(q);
  return p;
}
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  scanf("%s", str);
  for (int i = 1; i <= n; i++) {
    int cur = str[i - 1] - 'a' + 1;
    update(1, 1, n, i, i, cur);
  }
  while (q--) {
    int l, r, c;
    scanf("%d %d %d", &l, &r, &c);
    data ret = query(1, 1, n, l, r);
    if (c == 0) {
      int cur = l;
      for (int i = 26; i > 0; i--) {
        if (ret.cnt[i] > 0) {
          int x = ret.cnt[i];
          update(1, 1, n, cur, cur + x - 1, i);
          cur += x;
        }
      }
    } else {
      int cur = l;
      for (int i = 1; i <= 26; i++) {
        if (ret.cnt[i] > 0) {
          int x = ret.cnt[i];
          update(1, 1, n, cur, cur + x - 1, i);
          cur += x;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    data ret = query(1, 1, n, i, i);
    int pos = 0;
    while (ret.cnt[pos] == 0 && pos < 27) pos++;
    pos--;
    printf("%c", char('a' + pos));
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
char str[100005];
struct data {
  int cnt[27];
  int lazy;
  data() {
    memset(cnt, 0, sizeof(cnt));
    lazy = 0;
  }
  void clear() {
    lazy = 0;
    memset(cnt, 0, sizeof(cnt));
  }
  void add(data a) {
    for (int i = 1; i <= 26; i++) cnt[i] += a.cnt[i];
  }
};
data tree[6 * 100005];
void push_down(int n, int b, int e) {
  if (tree[n].lazy > 0) {
    int l = n * 2, r = l + 1, mid = (b + e) / 2;
    tree[l].clear();
    int x = tree[n].lazy;
    tree[l].lazy = x;
    int totall = mid - b + 1;
    tree[l].cnt[x] = totall;
    tree[r].clear();
    int totalr = e - mid;
    tree[r].lazy = x;
    tree[r].cnt[x] = totalr;
    tree[n].lazy = 0;
  }
  tree[n].lazy = 0;
}
void push_up(int n, int l, int r) {
  tree[n].clear();
  tree[n].add(tree[l]);
  tree[n].add(tree[r]);
}
void update(int n, int b, int e, int i, int j, int val) {
  if (b > j || e < i) return;
  if (b >= i && e <= j) {
    tree[n].clear();
    tree[n].lazy = val;
    int total = e - b + 1;
    tree[n].cnt[val] = total;
    return;
  }
  int l = n * 2, r = l + 1, mid = (b + e) / 2;
  push_down(n, b, e);
  update(l, b, mid, i, j, val);
  update(r, mid + 1, e, i, j, val);
  push_up(n, l, r);
}
data query(int n, int b, int e, int i, int j) {
  if (b > j || e < i) return tree[0];
  if (b >= i && e <= j) {
    return tree[n];
  }
  int l = n * 2, r = l + 1, mid = (b + e) / 2;
  push_down(n, b, e);
  data p = query(l, b, mid, i, j);
  data q = query(r, mid + 1, e, i, j);
  p.add(q);
  return p;
}
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  scanf("%s", str);
  for (int i = 1; i <= n; i++) {
    int cur = str[i - 1] - 'a' + 1;
    update(1, 1, n, i, i, cur);
  }
  while (q--) {
    int l, r, c;
    scanf("%d %d %d", &l, &r, &c);
    data ret = query(1, 1, n, l, r);
    if (c == 0) {
      int cur = l;
      for (int i = 26; i > 0; i--) {
        if (ret.cnt[i] > 0) {
          int x = ret.cnt[i];
          update(1, 1, n, cur, cur + x - 1, i);
          cur += x;
        }
      }
    } else {
      int cur = l;
      for (int i = 1; i <= 26; i++) {
        if (ret.cnt[i] > 0) {
          int x = ret.cnt[i];
          update(1, 1, n, cur, cur + x - 1, i);
          cur += x;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    data ret = query(1, 1, n, i, i);
    int pos = 0;
    while (ret.cnt[pos] == 0 && pos < 27) pos++;
    pos--;
    printf("%c", char('a' + pos));
  }
  return 0;
}

```