#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 17);
struct drvo {
  int cnt[2 * N + 100];
  int lzy[2 * N + 100];
  int sz[2 * N + 100];
  void init() {
    for (int i = N - 1; i > 0; i--) cnt[i] = cnt[2 * i] + cnt[2 * i + 1];
    for (int i = 0; i < N; i++) sz[i + N] = 1;
    for (int i = N - 1; i > 0; i--) sz[i] = sz[2 * i] + sz[2 * i + 1];
  }
  void push_lzy(int v) {
    if (!lzy[v]) return;
    if (lzy[v] == 1) cnt[v] = 0;
    if (lzy[v] == 2) cnt[v] = sz[v];
    if (v < N) {
      lzy[2 * v] = lzy[v];
      lzy[2 * v + 1] = lzy[v];
    }
    lzy[v] = 0;
  }
  void update(int l, int r, int a, int b, int v, int x) {
    push_lzy(v);
    if (l > b || r < a) return;
    if (l >= a && r <= b) {
      lzy[v] = x;
      push_lzy(v);
      return;
    }
    update(l, (l + r) / 2, a, b, 2 * v, x);
    update((l + r) / 2 + 1, r, a, b, 2 * v + 1, x);
    cnt[v] = cnt[2 * v] + cnt[2 * v + 1];
  }
  int get(int l, int r, int a, int b, int v) {
    push_lzy(v);
    if (l > b || r < a) return 0;
    if (l >= a && r <= b) return cnt[v];
    return get(l, (l + r) / 2, a, b, 2 * v) +
           get((l + r) / 2 + 1, r, a, b, 2 * v + 1);
  }
  void clear() {
    for (int i = 1; i <= 2 * N; i++) push_lzy(i);
  }
} sg[26];
char s[101000];
int nums[26];
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  scanf("%s", s);
  for (int i = 0; i < n; i++) sg[s[i] - 'a'].cnt[i + N]++;
  for (int i = 0; i < 26; i++) sg[i].init();
  while (q--) {
    int a, b, t;
    scanf("%d %d %d", &a, &b, &t);
    a--;
    b--;
    for (int i = 0; i < 26; i++) nums[i] = sg[i].get(0, N - 1, a, b, 1);
    for (int i = 0; i < 26; i++) sg[i].update(0, N - 1, a, b, 1, 1);
    if (t == 1)
      for (int i = 0; i < 26; i++) {
        if (!nums[i]) continue;
        sg[i].update(0, N - 1, a, a + nums[i] - 1, 1, 2);
        a += nums[i];
      }
    else
      for (int i = 25; i >= 0; i--) {
        if (!nums[i]) continue;
        sg[i].update(0, N - 1, a, a + nums[i] - 1, 1, 2);
        a += nums[i];
      }
  }
  for (int i = 0; i < 26; i++) sg[i].clear();
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 26; j++)
      if (sg[j].cnt[N + i]) printf("%c", 'a' + j);
  printf("\n");
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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 = (1 << 17);
struct drvo {
  int cnt[2 * N + 100];
  int lzy[2 * N + 100];
  int sz[2 * N + 100];
  void init() {
    for (int i = N - 1; i > 0; i--) cnt[i] = cnt[2 * i] + cnt[2 * i + 1];
    for (int i = 0; i < N; i++) sz[i + N] = 1;
    for (int i = N - 1; i > 0; i--) sz[i] = sz[2 * i] + sz[2 * i + 1];
  }
  void push_lzy(int v) {
    if (!lzy[v]) return;
    if (lzy[v] == 1) cnt[v] = 0;
    if (lzy[v] == 2) cnt[v] = sz[v];
    if (v < N) {
      lzy[2 * v] = lzy[v];
      lzy[2 * v + 1] = lzy[v];
    }
    lzy[v] = 0;
  }
  void update(int l, int r, int a, int b, int v, int x) {
    push_lzy(v);
    if (l > b || r < a) return;
    if (l >= a && r <= b) {
      lzy[v] = x;
      push_lzy(v);
      return;
    }
    update(l, (l + r) / 2, a, b, 2 * v, x);
    update((l + r) / 2 + 1, r, a, b, 2 * v + 1, x);
    cnt[v] = cnt[2 * v] + cnt[2 * v + 1];
  }
  int get(int l, int r, int a, int b, int v) {
    push_lzy(v);
    if (l > b || r < a) return 0;
    if (l >= a && r <= b) return cnt[v];
    return get(l, (l + r) / 2, a, b, 2 * v) +
           get((l + r) / 2 + 1, r, a, b, 2 * v + 1);
  }
  void clear() {
    for (int i = 1; i <= 2 * N; i++) push_lzy(i);
  }
} sg[26];
char s[101000];
int nums[26];
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  scanf("%s", s);
  for (int i = 0; i < n; i++) sg[s[i] - 'a'].cnt[i + N]++;
  for (int i = 0; i < 26; i++) sg[i].init();
  while (q--) {
    int a, b, t;
    scanf("%d %d %d", &a, &b, &t);
    a--;
    b--;
    for (int i = 0; i < 26; i++) nums[i] = sg[i].get(0, N - 1, a, b, 1);
    for (int i = 0; i < 26; i++) sg[i].update(0, N - 1, a, b, 1, 1);
    if (t == 1)
      for (int i = 0; i < 26; i++) {
        if (!nums[i]) continue;
        sg[i].update(0, N - 1, a, a + nums[i] - 1, 1, 2);
        a += nums[i];
      }
    else
      for (int i = 25; i >= 0; i--) {
        if (!nums[i]) continue;
        sg[i].update(0, N - 1, a, a + nums[i] - 1, 1, 2);
        a += nums[i];
      }
  }
  for (int i = 0; i < 26; i++) sg[i].clear();
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 26; j++)
      if (sg[j].cnt[N + i]) printf("%c", 'a' + j);
  printf("\n");
  return 0;
}

```