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>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
const int M = N << 2;
int cnt[26], n, m;
string str;
int L[M], R[M], sum[M][26], cover[M];
inline void pushup(int o) {
  for (int i = 0; i < 26; i++)
    sum[o][i] = sum[(o << 1)][i] + sum[((o << 1) | 1)][i];
}
void tag(int o, int c) {
  for (int i = 0; i < 26; i++) sum[o][i] = 0;
  sum[o][c] = R[o] - L[o] + 1;
  cover[o] = c;
}
inline void pushdown(int o) {
  if (cover[o] < 0 || L[o] == R[o]) return;
  tag((o << 1), cover[o]);
  tag(((o << 1) | 1), cover[o]);
  cover[o] = -1;
}
void build(int o, int l, int r) {
  L[o] = l;
  R[o] = r;
  cover[o] = -1;
  if (l == r) {
    sum[o][str[l - 1] - 'a'] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build((o << 1), l, mid);
  build(((o << 1) | 1), mid + 1, r);
  pushup(o);
}
void query(int o, int l, int r) {
  if (L[o] > r || R[o] < l) return;
  if (l <= L[o] && R[o] <= r) {
    for (int i = 0; i < 26; i++) cnt[i] += sum[o][i];
    return;
  }
  pushdown(o);
  query((o << 1), l, r);
  query(((o << 1) | 1), l, r);
}
void update(int o, int l, int r, int c) {
  if (L[o] > r || R[o] < l) return;
  if (l <= L[o] && R[o] <= r) {
    tag(o, c);
    return;
  }
  pushdown(o);
  update((o << 1), l, r, c);
  update(((o << 1) | 1), l, r, c);
  pushup(o);
}
void dfs(int o) {
  if (L[o] == R[o]) {
    int j = 0;
    for (int i = 0; i < 26; i++)
      if (sum[o][i] > 0) {
        j = i;
        break;
      }
    cout << char(j + 'a');
    return;
  }
  pushdown(o);
  dfs((o << 1));
  dfs(((o << 1) | 1));
}
int main() {
  ios::sync_with_stdio(0);
  cin >> n >> m >> str;
  build(1, 1, n);
  while (m--) {
    int l, r, k;
    cin >> l >> r >> k;
    for (int i = 0; i < 26; i++) cnt[i] = 0;
    query(1, l, r);
    if (k == 1) {
      int p = l, q = 0;
      for (int i = 0; i < 26; i++)
        if (cnt[i]) {
          q = p + cnt[i] - 1;
          update(1, p, q, i);
          p = q + 1;
        }
    } else {
      int p = l, q = 0;
      for (int i = 25; i >= 0; i--)
        if (cnt[i]) {
          q = p + cnt[i] - 1;
          update(1, p, q, i);
          p = q + 1;
        }
    }
  }
  dfs(1);
  cout << endl;
  return 0;
}