#include <bits/stdc++.h>
using namespace std;
struct Ret {
  int ret[26];
  void operator+=(const Ret &r) {
    for (int i = 0; i < 26; ++i) {
      ret[i] += r.ret[i];
    }
  }
};
int sum[26][111111 << 2], tag[26][111111 << 2];
int N, x, y, z;
Ret query(int i, int j, int k) {
  if (x <= i && j <= y) {
    Ret r = {0};
    for (int t = 0; t < 26; ++t) r.ret[t] += sum[t][k];
    return r;
  }
  int mid = i + j >> 1;
  for (int t = 0; t < 26; ++t) {
    if (tag[t][k]) {
      tag[t][k << 1] = tag[t][k];
      tag[t][k << 1 | 1] = tag[t][k];
      if (tag[t][k] == 1) {
        sum[t][k << 1] = mid - i + 1;
        sum[t][k << 1 | 1] = j - mid;
      } else {
        sum[t][k << 1] = 0;
        sum[t][k << 1 | 1] = 0;
      }
      tag[t][k] = 0;
    }
  }
  Ret r = {0};
  if (x <= mid) r += query(i, mid, k << 1);
  if (y > mid) r += query(mid + 1, j, k << 1 | 1);
  return r;
}
void update(int i, int j, int k, int flag) {
  if (x > y) return;
  if (x <= i && j <= y) {
    tag[z][k] = flag;
    if (flag == 1)
      sum[z][k] = j - i + 1;
    else
      sum[z][k] = 0;
    return;
  }
  int mid = i + j >> 1;
  if (tag[z][k]) {
    tag[z][k << 1] = tag[z][k];
    tag[z][k << 1 | 1] = tag[z][k];
    if (tag[z][k] == 1) {
      sum[z][k << 1] = mid - i + 1;
      sum[z][k << 1 | 1] = j - mid;
    } else {
      sum[z][k << 1] = 0;
      sum[z][k << 1 | 1] = 0;
    }
    tag[z][k] = 0;
  }
  if (x <= mid) update(i, mid, k << 1, flag);
  if (y > mid) update(mid + 1, j, k << 1 | 1, flag);
  sum[z][k] = sum[z][k << 1] + sum[z][k << 1 | 1];
}
char str[111111];
int main() {
  int n, m;
  scanf("%d%d%s", &n, &m, str + 1);
  for (N = 1; N < n; N <<= 1)
    ;
  for (int i = 1; i <= n; ++i) {
    x = i;
    y = i;
    z = str[i] - 'a';
    update(1, N, 1, 1);
  }
  int a;
  while (m--) {
    scanf("%d%d%d", &x, &y, &a);
    Ret r = query(1, N, 1);
    for (z = 0; z < 26; ++z) {
      update(1, N, 1, -1);
    }
    if (a == 1) {
      int now = x;
      for (z = 0; z < 26; ++z) {
        x = now;
        y = now + r.ret[z] - 1;
        update(1, N, 1, 1);
        now += r.ret[z];
      }
    } else {
      int now = x;
      for (z = 25; z >= 0; --z) {
        x = now;
        y = now + r.ret[z] - 1;
        update(1, N, 1, 1);
        now += r.ret[z];
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    x = i;
    y = i;
    Ret r = query(1, N, 1);
    for (int j = 0; j < 26; ++j) {
      if (r.ret[j]) putchar(j + 'a');
    }
  }
  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;
struct Ret {
  int ret[26];
  void operator+=(const Ret &r) {
    for (int i = 0; i < 26; ++i) {
      ret[i] += r.ret[i];
    }
  }
};
int sum[26][111111 << 2], tag[26][111111 << 2];
int N, x, y, z;
Ret query(int i, int j, int k) {
  if (x <= i && j <= y) {
    Ret r = {0};
    for (int t = 0; t < 26; ++t) r.ret[t] += sum[t][k];
    return r;
  }
  int mid = i + j >> 1;
  for (int t = 0; t < 26; ++t) {
    if (tag[t][k]) {
      tag[t][k << 1] = tag[t][k];
      tag[t][k << 1 | 1] = tag[t][k];
      if (tag[t][k] == 1) {
        sum[t][k << 1] = mid - i + 1;
        sum[t][k << 1 | 1] = j - mid;
      } else {
        sum[t][k << 1] = 0;
        sum[t][k << 1 | 1] = 0;
      }
      tag[t][k] = 0;
    }
  }
  Ret r = {0};
  if (x <= mid) r += query(i, mid, k << 1);
  if (y > mid) r += query(mid + 1, j, k << 1 | 1);
  return r;
}
void update(int i, int j, int k, int flag) {
  if (x > y) return;
  if (x <= i && j <= y) {
    tag[z][k] = flag;
    if (flag == 1)
      sum[z][k] = j - i + 1;
    else
      sum[z][k] = 0;
    return;
  }
  int mid = i + j >> 1;
  if (tag[z][k]) {
    tag[z][k << 1] = tag[z][k];
    tag[z][k << 1 | 1] = tag[z][k];
    if (tag[z][k] == 1) {
      sum[z][k << 1] = mid - i + 1;
      sum[z][k << 1 | 1] = j - mid;
    } else {
      sum[z][k << 1] = 0;
      sum[z][k << 1 | 1] = 0;
    }
    tag[z][k] = 0;
  }
  if (x <= mid) update(i, mid, k << 1, flag);
  if (y > mid) update(mid + 1, j, k << 1 | 1, flag);
  sum[z][k] = sum[z][k << 1] + sum[z][k << 1 | 1];
}
char str[111111];
int main() {
  int n, m;
  scanf("%d%d%s", &n, &m, str + 1);
  for (N = 1; N < n; N <<= 1)
    ;
  for (int i = 1; i <= n; ++i) {
    x = i;
    y = i;
    z = str[i] - 'a';
    update(1, N, 1, 1);
  }
  int a;
  while (m--) {
    scanf("%d%d%d", &x, &y, &a);
    Ret r = query(1, N, 1);
    for (z = 0; z < 26; ++z) {
      update(1, N, 1, -1);
    }
    if (a == 1) {
      int now = x;
      for (z = 0; z < 26; ++z) {
        x = now;
        y = now + r.ret[z] - 1;
        update(1, N, 1, 1);
        now += r.ret[z];
      }
    } else {
      int now = x;
      for (z = 25; z >= 0; --z) {
        x = now;
        y = now + r.ret[z] - 1;
        update(1, N, 1, 1);
        now += r.ret[z];
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    x = i;
    y = i;
    Ret r = query(1, N, 1);
    for (int j = 0; j < 26; ++j) {
      if (r.ret[j]) putchar(j + 'a');
    }
  }
  return 0;
}

```