#include <bits/stdc++.h>
using namespace std;
char str[100010];
const int SZ = 333;
int A[SZ][30];
int minn[SZ];
int maxx[SZ];
int gao[30];
int f[SZ];
int main() {
  ios::sync_with_stdio(false);
  for (int i = 0; i < SZ; i++) {
    minn[i] = 0x3FFFFFFF;
    maxx[i] = -0x3FFFFFFF;
  }
  for (int i = 0; i < SZ; i++) f[i] = 2;
  int n, q;
  scanf("%d%d", &n, &q);
  scanf("%s", str);
  int tot = (n - 1) / SZ + 1;
  for (int i = 0; i < n; i++) {
    int j = i / SZ;
    str[i] -= 'a';
    A[j][str[i]]++;
    minn[j] = min(minn[j], i);
    maxx[j] = max(maxx[j], i);
  }
  for (int i = 0; i < q; i++) {
    int l, r, c;
    scanf("%d%d%d", &l, &r, &c);
    l--;
    r--;
    int tl = l;
    int tr = r;
    memset(gao, 0, sizeof(gao));
    for (int j = 0; j < tot; j++) {
      l = max(minn[j], tl);
      r = min(maxx[j], tr);
      if (l == minn[j] && r == maxx[j]) {
        for (int k = 0; k < 26; k++) {
          gao[k] += A[j][k];
          A[j][k] = 0;
        }
      } else if (r >= l) {
        if (f[j] == 1) {
          int x = minn[j];
          for (int k = 0; k < 26; k++) {
            int num = A[j][k];
            while (num--) {
              str[x] = k;
              x++;
            }
          }
        } else if (f[j] == 0) {
          int x = maxx[j];
          for (int k = 0; k < 26; k++) {
            int num = A[j][k];
            while (num--) {
              str[x] = k;
              x--;
            }
          }
        }
        f[j] = 2;
        for (int k = l; k <= r; k++) {
          gao[str[k]]++;
          A[j][str[k]]--;
        }
      }
    }
    for (int j = 0; j < tot; j++) {
      l = max(minn[j], tl);
      r = min(maxx[j], tr);
      if (l == minn[j] && r == maxx[j]) {
        if (c) {
          int len = r - l + 1;
          for (int k = 0; k < 26; k++) {
            int tmp = min(len, gao[k]);
            len -= tmp;
            A[j][k] += tmp;
            gao[k] -= tmp;
          }
        } else {
          int len = r - l + 1;
          for (int k = 25; k >= 0; k--) {
            int tmp = min(len, gao[k]);
            len -= tmp;
            A[j][k] += tmp;
            gao[k] -= tmp;
          }
        }
        f[j] = c;
      } else if (r >= l) {
        if (c) {
          int x = l;
          for (int k = 0; k < 26; k++) {
            while (x <= r && gao[k]) {
              gao[k]--;
              str[x] = k;
              x++;
              A[j][k]++;
            }
          }
        } else {
          int x = l;
          for (int k = 25; k >= 0; k--) {
            while (x <= r && gao[k]) {
              gao[k]--;
              str[x] = k;
              x++;
              A[j][k]++;
            }
          }
        }
      }
    }
  }
  for (int i = 0; i < tot; i++) {
    if (f[i] == 2) continue;
    if (f[i] == 1) {
      int x = minn[i];
      for (int k = 0; k < 26; k++) {
        int num = A[i][k];
        while (num--) {
          str[x] = k;
          x++;
        }
      }
    } else if (f[i] == 0) {
      int x = maxx[i];
      for (int k = 0; k < 26; k++) {
        int num = A[i][k];
        while (num--) {
          str[x] = k;
          x--;
        }
      }
    }
  }
  for (int i = 0; i < n; i++) printf("%c", str[i] + 'a');
  printf("\n");
  return 0;
}

### Prompt

In CPP, your task is to solve 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;
char str[100010];
const int SZ = 333;
int A[SZ][30];
int minn[SZ];
int maxx[SZ];
int gao[30];
int f[SZ];
int main() {
  ios::sync_with_stdio(false);
  for (int i = 0; i < SZ; i++) {
    minn[i] = 0x3FFFFFFF;
    maxx[i] = -0x3FFFFFFF;
  }
  for (int i = 0; i < SZ; i++) f[i] = 2;
  int n, q;
  scanf("%d%d", &n, &q);
  scanf("%s", str);
  int tot = (n - 1) / SZ + 1;
  for (int i = 0; i < n; i++) {
    int j = i / SZ;
    str[i] -= 'a';
    A[j][str[i]]++;
    minn[j] = min(minn[j], i);
    maxx[j] = max(maxx[j], i);
  }
  for (int i = 0; i < q; i++) {
    int l, r, c;
    scanf("%d%d%d", &l, &r, &c);
    l--;
    r--;
    int tl = l;
    int tr = r;
    memset(gao, 0, sizeof(gao));
    for (int j = 0; j < tot; j++) {
      l = max(minn[j], tl);
      r = min(maxx[j], tr);
      if (l == minn[j] && r == maxx[j]) {
        for (int k = 0; k < 26; k++) {
          gao[k] += A[j][k];
          A[j][k] = 0;
        }
      } else if (r >= l) {
        if (f[j] == 1) {
          int x = minn[j];
          for (int k = 0; k < 26; k++) {
            int num = A[j][k];
            while (num--) {
              str[x] = k;
              x++;
            }
          }
        } else if (f[j] == 0) {
          int x = maxx[j];
          for (int k = 0; k < 26; k++) {
            int num = A[j][k];
            while (num--) {
              str[x] = k;
              x--;
            }
          }
        }
        f[j] = 2;
        for (int k = l; k <= r; k++) {
          gao[str[k]]++;
          A[j][str[k]]--;
        }
      }
    }
    for (int j = 0; j < tot; j++) {
      l = max(minn[j], tl);
      r = min(maxx[j], tr);
      if (l == minn[j] && r == maxx[j]) {
        if (c) {
          int len = r - l + 1;
          for (int k = 0; k < 26; k++) {
            int tmp = min(len, gao[k]);
            len -= tmp;
            A[j][k] += tmp;
            gao[k] -= tmp;
          }
        } else {
          int len = r - l + 1;
          for (int k = 25; k >= 0; k--) {
            int tmp = min(len, gao[k]);
            len -= tmp;
            A[j][k] += tmp;
            gao[k] -= tmp;
          }
        }
        f[j] = c;
      } else if (r >= l) {
        if (c) {
          int x = l;
          for (int k = 0; k < 26; k++) {
            while (x <= r && gao[k]) {
              gao[k]--;
              str[x] = k;
              x++;
              A[j][k]++;
            }
          }
        } else {
          int x = l;
          for (int k = 25; k >= 0; k--) {
            while (x <= r && gao[k]) {
              gao[k]--;
              str[x] = k;
              x++;
              A[j][k]++;
            }
          }
        }
      }
    }
  }
  for (int i = 0; i < tot; i++) {
    if (f[i] == 2) continue;
    if (f[i] == 1) {
      int x = minn[i];
      for (int k = 0; k < 26; k++) {
        int num = A[i][k];
        while (num--) {
          str[x] = k;
          x++;
        }
      }
    } else if (f[i] == 0) {
      int x = maxx[i];
      for (int k = 0; k < 26; k++) {
        int num = A[i][k];
        while (num--) {
          str[x] = k;
          x--;
        }
      }
    }
  }
  for (int i = 0; i < n; i++) printf("%c", str[i] + 'a');
  printf("\n");
  return 0;
}

```