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>
struct Node {
  int seg[100005 << 2], add[100005 << 2], mul[100005 << 2];
  inline void pushup(int rt) { seg[rt] = seg[(rt << 1)] + seg[(rt << 1 | 1)]; }
  inline void pushdown(int rt, int sizel, int sizer) {
    if (mul[rt]) {
      add[(rt << 1)] = add[(rt << 1 | 1)] = seg[(rt << 1)] =
          seg[(rt << 1 | 1)] = 0;
      mul[(rt << 1)] = mul[(rt << 1 | 1)] = 1;
      mul[rt] = 0;
    }
    seg[(rt << 1)] += sizel * add[rt];
    seg[(rt << 1 | 1)] += sizer * add[rt];
    add[(rt << 1)] += add[rt];
    add[(rt << 1 | 1)] += add[rt];
    add[rt] = 0;
  }
  void update(int L, int R, int C, int rt, int l, int r) {
    if (L <= l && R >= r) {
      seg[rt] += (r - l + 1) * C;
      add[rt] += C;
      return;
    }
    if (L > r || R < l) return;
    int mid = (l + r) >> 1;
    pushdown(rt, mid - l + 1, r - mid);
    if (L <= mid) update(L, R, C, (rt << 1), l, mid);
    if (R > mid) update(L, R, C, (rt << 1 | 1), mid + 1, r);
    pushup(rt);
  }
  void reset(int L, int R, int rt, int l, int r) {
    if (L <= l && R >= r) {
      seg[rt] = 0;
      mul[rt] = 1;
      add[rt] = 0;
      return;
    }
    if (L > r || R < l) return;
    int mid = (l + r) >> 1;
    pushdown(rt, mid - l + 1, r - mid);
    if (L <= mid) reset(L, R, (rt << 1), l, mid);
    if (R > mid) reset(L, R, (rt << 1 | 1), mid + 1, r);
    pushup(rt);
  }
  int query(int L, int R, int rt, int l, int r) {
    if (L <= l && R >= r) return seg[rt];
    if (L > r || R < l) return 0;
    int mid = (l + r) >> 1;
    pushdown(rt, mid - l + 1, r - mid);
    int ans = 0;
    if (L <= mid) ans += query(L, R, (rt << 1), l, mid);
    if (R > mid) ans += query(L, R, (rt << 1 | 1), mid + 1, r);
    return ans;
  }
} S[30];
int book[30];
int N, M;
inline char read() {
  char ch = getchar();
  while (ch > 'z' || ch < 'a') ch = getchar();
  return ch;
}
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; ++i) S[read() - 'a' + 1].update(i, i, 1, 1, 1, N);
  int L, R, K;
  for (int k = 1; k <= M; ++k) {
    scanf("%d%d%d", &L, &R, &K);
    std::memset(book, 0, sizeof(book));
    for (int i = 1; i <= 26; ++i) {
      book[i] = S[i].query(L, R, 1, 1, N);
      S[i].reset(L, R, 1, 1, N);
    }
    int sum = 0;
    if (K == 1) {
      for (int i = 1; i <= 26; ++i) {
        S[i].update(L + sum, L + sum + book[i] - 1, 1, 1, 1, N);
        sum += book[i];
      }
    } else {
      for (int i = 26; i >= 1; --i) {
        S[i].update(L + sum, L + sum + book[i] - 1, 1, 1, 1, N);
        sum += book[i];
      }
    }
  }
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= 26; ++j) {
      if (S[j].query(i, i, 1, 1, N) == 1) {
        putchar(j + 'a' - 1);
        break;
      }
    }
  }
  return 0;
}