#include <bits/stdc++.h>
using namespace std;
int n, q;
char s[100005];
int Cnt[26];
int Res[100005];
struct Seg {
  int Sum;
  pair<bool, int> Cov;
  Seg() { Cov = make_pair(false, 0); }
  Seg(int S, pair<bool, int> C) {
    Sum = S;
    Cov = C;
  }
} T[26][400005];
int Alpha, a[100005];
inline void Update(int pos) {
  T[Alpha][pos].Sum = T[Alpha][pos << 1].Sum + T[Alpha][pos << 1 | 1].Sum;
}
int L, R, K;
void Build(int Pos, int l, int r) {
  if (l == r) {
    T[Alpha][Pos].Sum = (Alpha == a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  Build(Pos << 1, l, mid), Build(Pos << 1 | 1, mid + 1, r);
  Update(Pos);
}
inline void Down(int Pos, int l, int r) {
  T[Alpha][Pos << 1].Cov = T[Alpha][Pos << 1 | 1].Cov = T[Alpha][Pos].Cov;
  int mid = (l + r) >> 1;
  T[Alpha][Pos << 1].Sum = (mid - l + 1) * T[Alpha][Pos].Cov.second;
  T[Alpha][Pos << 1 | 1].Sum = (r - mid) * T[Alpha][Pos].Cov.second;
  T[Alpha][Pos].Cov.first = false;
}
int Count(int Pos, int l, int r) {
  if (L <= l && r <= R) return T[Alpha][Pos].Sum;
  if (T[Alpha][Pos].Cov.first) Down(Pos, l, r);
  int mid = (l + r) >> 1, Res = 0;
  if (L <= mid) Res += Count(Pos << 1, l, mid);
  if (R > mid) Res += Count(Pos << 1 | 1, mid + 1, r);
  return Res;
}
void Clear(int Pos, int l, int r) {
  if (L <= l && r <= R) {
    T[Alpha][Pos] = Seg((r - l + 1) * K, make_pair(true, K));
    return;
  }
  if (T[Alpha][Pos].Cov.first) Down(Pos, l, r);
  int mid = (l + r) >> 1;
  if (L <= mid) Clear(Pos << 1, l, mid);
  if (R > mid) Clear(Pos << 1 | 1, mid + 1, r);
  Update(Pos);
}
void Get_Res(int Pos, int l, int r) {
  if (!T[Alpha][Pos].Sum) return;
  if (l == r) {
    Res[l] = Alpha;
    return;
  }
  if (T[Alpha][Pos].Cov.first) Down(Pos, l, r);
  int mid = (l + r) >> 1;
  Get_Res(Pos << 1, l, mid), Get_Res(Pos << 1 | 1, mid + 1, r);
}
int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", s);
  for (int i = 1; i <= n; i++) a[i] = s[i - 1] - 'a';
  for (int i = 0; i < 26; i++) Alpha = i, Build(1, 1, n);
  for (int k; q; q--) {
    scanf("%d%d%d", &L, &R, &k);
    ::K = 0;
    for (int i = 0; i < 26; i++) {
      Alpha = i, Cnt[Alpha] = Count(1, 1, n);
      Clear(1, 1, n);
    }
    ::K = 1;
    if (k) {
      for (Alpha = 0; Alpha < 26; Alpha++)
        if (Cnt[Alpha]) {
          ::R = ::L + Cnt[Alpha] - 1;
          Clear(1, 1, n);
          ::L += Cnt[Alpha];
        }
    } else {
      for (Alpha = 25; ~Alpha; Alpha--)
        if (Cnt[Alpha]) {
          ::R = ::L + Cnt[Alpha] - 1;
          Clear(1, 1, n);
          ::L += Cnt[Alpha];
        }
    }
  }
  for (Alpha = 0; Alpha < 26; Alpha++) Get_Res(1, 1, n);
  for (int i = 1; i <= n; i++) putchar('a' + Res[i]);
  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;
int n, q;
char s[100005];
int Cnt[26];
int Res[100005];
struct Seg {
  int Sum;
  pair<bool, int> Cov;
  Seg() { Cov = make_pair(false, 0); }
  Seg(int S, pair<bool, int> C) {
    Sum = S;
    Cov = C;
  }
} T[26][400005];
int Alpha, a[100005];
inline void Update(int pos) {
  T[Alpha][pos].Sum = T[Alpha][pos << 1].Sum + T[Alpha][pos << 1 | 1].Sum;
}
int L, R, K;
void Build(int Pos, int l, int r) {
  if (l == r) {
    T[Alpha][Pos].Sum = (Alpha == a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  Build(Pos << 1, l, mid), Build(Pos << 1 | 1, mid + 1, r);
  Update(Pos);
}
inline void Down(int Pos, int l, int r) {
  T[Alpha][Pos << 1].Cov = T[Alpha][Pos << 1 | 1].Cov = T[Alpha][Pos].Cov;
  int mid = (l + r) >> 1;
  T[Alpha][Pos << 1].Sum = (mid - l + 1) * T[Alpha][Pos].Cov.second;
  T[Alpha][Pos << 1 | 1].Sum = (r - mid) * T[Alpha][Pos].Cov.second;
  T[Alpha][Pos].Cov.first = false;
}
int Count(int Pos, int l, int r) {
  if (L <= l && r <= R) return T[Alpha][Pos].Sum;
  if (T[Alpha][Pos].Cov.first) Down(Pos, l, r);
  int mid = (l + r) >> 1, Res = 0;
  if (L <= mid) Res += Count(Pos << 1, l, mid);
  if (R > mid) Res += Count(Pos << 1 | 1, mid + 1, r);
  return Res;
}
void Clear(int Pos, int l, int r) {
  if (L <= l && r <= R) {
    T[Alpha][Pos] = Seg((r - l + 1) * K, make_pair(true, K));
    return;
  }
  if (T[Alpha][Pos].Cov.first) Down(Pos, l, r);
  int mid = (l + r) >> 1;
  if (L <= mid) Clear(Pos << 1, l, mid);
  if (R > mid) Clear(Pos << 1 | 1, mid + 1, r);
  Update(Pos);
}
void Get_Res(int Pos, int l, int r) {
  if (!T[Alpha][Pos].Sum) return;
  if (l == r) {
    Res[l] = Alpha;
    return;
  }
  if (T[Alpha][Pos].Cov.first) Down(Pos, l, r);
  int mid = (l + r) >> 1;
  Get_Res(Pos << 1, l, mid), Get_Res(Pos << 1 | 1, mid + 1, r);
}
int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", s);
  for (int i = 1; i <= n; i++) a[i] = s[i - 1] - 'a';
  for (int i = 0; i < 26; i++) Alpha = i, Build(1, 1, n);
  for (int k; q; q--) {
    scanf("%d%d%d", &L, &R, &k);
    ::K = 0;
    for (int i = 0; i < 26; i++) {
      Alpha = i, Cnt[Alpha] = Count(1, 1, n);
      Clear(1, 1, n);
    }
    ::K = 1;
    if (k) {
      for (Alpha = 0; Alpha < 26; Alpha++)
        if (Cnt[Alpha]) {
          ::R = ::L + Cnt[Alpha] - 1;
          Clear(1, 1, n);
          ::L += Cnt[Alpha];
        }
    } else {
      for (Alpha = 25; ~Alpha; Alpha--)
        if (Cnt[Alpha]) {
          ::R = ::L + Cnt[Alpha] - 1;
          Clear(1, 1, n);
          ::L += Cnt[Alpha];
        }
    }
  }
  for (Alpha = 0; Alpha < 26; Alpha++) Get_Res(1, 1, n);
  for (int i = 1; i <= n; i++) putchar('a' + Res[i]);
  return 0;
}

```