#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int maxn = 111111;
const int MAXN = 400010;
class Seg {
 public:
  int *a, n;
  long long s[MAXN];
  int setv[MAXN];
  void modify(int o, int l, int r) {
    if (setv[o] >= 0) {
      s[o] = (r - l + 1) * setv[o];
    } else {
      if (l == r)
        s[o] = a[l];
      else
        s[o] = s[2 * o] + s[2 * o + 1];
    }
  }
  void Init(int *_a, int _n) {
    n = _n;
    a = _a;
    fill(setv, setv + MAXN, -1);
    init(1, 1, n);
  }
  void init(int o, int l, int r) {
    if (l == r) {
      s[o] = a[l];
      return;
    }
    int m = l + (r - l) / 2;
    init(2 * o, l, m);
    init(2 * o + 1, m + 1, r);
    modify(o, l, r);
  }
  void setR(int o, int l, int r, int ql, int qr, int v) {
    if (l == r) {
      setv[o] = v;
      a[l] = v;
      s[o] = v;
      return;
    }
    if (ql <= l && qr >= r) {
      setv[o] = v;
      modify(o, l, r);
      return;
    }
    if (setv[o] >= 0) {
      setv[2 * o] = setv[o];
      setv[2 * o + 1] = setv[o];
      setv[o] = -1;
    }
    int m = l + (r - l) / 2;
    if (ql <= m)
      setR(2 * o, l, m, ql, qr, v);
    else
      modify(2 * o, l, m);
    if (qr > m)
      setR(2 * o + 1, m + 1, r, ql, qr, v);
    else
      modify(2 * o + 1, m + 1, r);
    modify(o, l, r);
  }
  long long get_sum(int o, int l, int r, int ql, int qr) {
    if (setv[o] >= 0) {
      return setv[o] * (min(r, qr) - max(l, ql) + 1);
    }
    if (ql <= l && qr >= r) return s[o];
    int m = l + (r - l) / 2;
    if (qr <= m)
      return get_sum(2 * o, l, m, ql, qr);
    else if (ql > m)
      return get_sum(2 * o + 1, m + 1, r, ql, qr);
    else {
      return get_sum(2 * o, l, m, ql, qr) +
             get_sum(2 * o + 1, m + 1, r, ql, qr);
    }
  }
  void print() {
    for (int i = 1; i <= n; ++i) printf("%d%c", a[i], " \n"[i == n]);
  }
} seq[26];
char str[maxn];
int cnt[26][maxn];
int n, m;
int work[26];
int main(int argc, char const *argv[]) {
  scanf("%d%d", &(n), &(m));
  scanf("%s", (str));
  for (int(i) = 0; i < (int)(n); ++(i)) {
    int idx = str[i] - 'a';
    cnt[idx][i + 1] = 1;
  }
  for (int(i) = 0; i < (int)(26); ++(i)) seq[i].Init(cnt[i], n);
  while (m--) {
    int l, r, t;
    scanf("%d%d%d", &(l), &(r), &(t));
    memset(work, 0, sizeof(work));
    for (int(i) = 0; i < (int)(26); ++(i)) {
      work[i] = seq[i].get_sum(1, 1, n, l, r);
      seq[i].setR(1, 1, n, l, r, 0);
    }
    int from = l;
    if (t == 1) {
      for (int(i) = 0; i < (int)(26); ++(i))
        if (work[i] > 0) {
          seq[i].setR(1, 1, n, from, from + work[i] - 1, 1);
          from += work[i];
        }
    } else {
      for (int i = 25; i >= 0; --i)
        if (work[i] > 0) {
          seq[i].setR(1, 1, n, from, from + work[i] - 1, 1);
          from += work[i];
        }
    }
  }
  for (int(j) = 0; j < (int)(n); ++(j)) str[j] = 'z';
  for (int(i) = 0; i < (int)(26); ++(i))
    for (int(j) = 0; j < (int)(n); ++(j))
      if (seq[i].get_sum(1, 1, n, j + 1, j + 1) == 1) str[j] = 'a' + i;
  puts(str);
  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;
const int MOD = 1e9 + 7;
const int maxn = 111111;
const int MAXN = 400010;
class Seg {
 public:
  int *a, n;
  long long s[MAXN];
  int setv[MAXN];
  void modify(int o, int l, int r) {
    if (setv[o] >= 0) {
      s[o] = (r - l + 1) * setv[o];
    } else {
      if (l == r)
        s[o] = a[l];
      else
        s[o] = s[2 * o] + s[2 * o + 1];
    }
  }
  void Init(int *_a, int _n) {
    n = _n;
    a = _a;
    fill(setv, setv + MAXN, -1);
    init(1, 1, n);
  }
  void init(int o, int l, int r) {
    if (l == r) {
      s[o] = a[l];
      return;
    }
    int m = l + (r - l) / 2;
    init(2 * o, l, m);
    init(2 * o + 1, m + 1, r);
    modify(o, l, r);
  }
  void setR(int o, int l, int r, int ql, int qr, int v) {
    if (l == r) {
      setv[o] = v;
      a[l] = v;
      s[o] = v;
      return;
    }
    if (ql <= l && qr >= r) {
      setv[o] = v;
      modify(o, l, r);
      return;
    }
    if (setv[o] >= 0) {
      setv[2 * o] = setv[o];
      setv[2 * o + 1] = setv[o];
      setv[o] = -1;
    }
    int m = l + (r - l) / 2;
    if (ql <= m)
      setR(2 * o, l, m, ql, qr, v);
    else
      modify(2 * o, l, m);
    if (qr > m)
      setR(2 * o + 1, m + 1, r, ql, qr, v);
    else
      modify(2 * o + 1, m + 1, r);
    modify(o, l, r);
  }
  long long get_sum(int o, int l, int r, int ql, int qr) {
    if (setv[o] >= 0) {
      return setv[o] * (min(r, qr) - max(l, ql) + 1);
    }
    if (ql <= l && qr >= r) return s[o];
    int m = l + (r - l) / 2;
    if (qr <= m)
      return get_sum(2 * o, l, m, ql, qr);
    else if (ql > m)
      return get_sum(2 * o + 1, m + 1, r, ql, qr);
    else {
      return get_sum(2 * o, l, m, ql, qr) +
             get_sum(2 * o + 1, m + 1, r, ql, qr);
    }
  }
  void print() {
    for (int i = 1; i <= n; ++i) printf("%d%c", a[i], " \n"[i == n]);
  }
} seq[26];
char str[maxn];
int cnt[26][maxn];
int n, m;
int work[26];
int main(int argc, char const *argv[]) {
  scanf("%d%d", &(n), &(m));
  scanf("%s", (str));
  for (int(i) = 0; i < (int)(n); ++(i)) {
    int idx = str[i] - 'a';
    cnt[idx][i + 1] = 1;
  }
  for (int(i) = 0; i < (int)(26); ++(i)) seq[i].Init(cnt[i], n);
  while (m--) {
    int l, r, t;
    scanf("%d%d%d", &(l), &(r), &(t));
    memset(work, 0, sizeof(work));
    for (int(i) = 0; i < (int)(26); ++(i)) {
      work[i] = seq[i].get_sum(1, 1, n, l, r);
      seq[i].setR(1, 1, n, l, r, 0);
    }
    int from = l;
    if (t == 1) {
      for (int(i) = 0; i < (int)(26); ++(i))
        if (work[i] > 0) {
          seq[i].setR(1, 1, n, from, from + work[i] - 1, 1);
          from += work[i];
        }
    } else {
      for (int i = 25; i >= 0; --i)
        if (work[i] > 0) {
          seq[i].setR(1, 1, n, from, from + work[i] - 1, 1);
          from += work[i];
        }
    }
  }
  for (int(j) = 0; j < (int)(n); ++(j)) str[j] = 'z';
  for (int(i) = 0; i < (int)(26); ++(i))
    for (int(j) = 0; j < (int)(n); ++(j))
      if (seq[i].get_sum(1, 1, n, j + 1, j + 1) == 1) str[j] = 'a' + i;
  puts(str);
  return 0;
}

```