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 = 100005;
const int sigma = 26;
int sumv[N << 2][sigma], setv[N << 2];
int cnt[26];
char str[N];
void pushUp(int o) {
  for (int i = 0; i < sigma; i++) {
    sumv[o][i] = sumv[(o << 1)][i] + sumv[(o << 1 | 1)][i];
  }
}
void initNode(int o) { memset(sumv[o], 0, sizeof(sumv[o])); }
void pushDown(int o, int L, int R) {
  int M = (L + R) / 2;
  if (setv[o] != -1) {
    setv[(o << 1)] = setv[(o << 1 | 1)] = setv[o];
    initNode((o << 1));
    sumv[(o << 1)][setv[o]] = (M - L + 1);
    initNode((o << 1 | 1));
    sumv[(o << 1 | 1)][setv[o]] = (R - M);
    setv[o] = -1;
  }
}
void build(int o, int L, int R) {
  if (L == R) {
    initNode(o);
    sumv[o][str[L] - 'a'] = 1;
    setv[o] = str[L] - 'a';
    return;
  }
  setv[o] = -1;
  int M = (L + R) / 2;
  build((o << 1), L, M);
  build((o << 1 | 1), M + 1, R);
  pushUp(o);
}
int query(int o, int L, int R, int ql, int qr, int val) {
  if (ql <= L && R <= qr) return sumv[o][val];
  pushDown(o, L, R);
  int M = (L + R) / 2, ret = 0;
  if (ql <= M) ret += query((o << 1), L, M, ql, qr, val);
  if (qr > M) ret += query((o << 1 | 1), M + 1, R, ql, qr, val);
  return ret;
}
void modify(int o, int L, int R, int ql, int qr, int val) {
  if (ql <= L && R <= qr) {
    for (int i = 0; i < sigma; i++) sumv[o][i] = 0;
    setv[o] = val;
    sumv[o][setv[o]] = (R - L + 1);
    return;
  }
  pushDown(o, L, R);
  int M = (L + R) / 2;
  if (ql <= M) modify((o << 1), L, M, ql, qr, val);
  if (qr > M) modify((o << 1 | 1), M + 1, R, ql, qr, val);
  pushUp(o);
}
void getStr(int o, int L, int R) {
  if (L == R) {
    printf("%c", (char)('a' + setv[o]));
    return;
  }
  pushDown(o, L, R);
  int M = (L + R) / 2;
  getStr((o << 1), L, M);
  getStr((o << 1 | 1), M + 1, R);
}
int n, q;
int main() {
  while (scanf("%d%d", &n, &q) != EOF) {
    scanf("%s", str + 1);
    build(1, 1, n);
    int ql, qr, ch;
    while (q--) {
      scanf("%d%d%d", &ql, &qr, &ch);
      for (int i = 0; i < sigma; i++) cnt[i] = query(1, 1, n, ql, qr, i);
      int pos = ql;
      if (ch == 1) {
        for (int i = 0; i < sigma; i++) {
          if (cnt[i] > 0) modify(1, 1, n, pos, pos + cnt[i] - 1, i);
          pos += cnt[i];
        }
      } else {
        for (int i = sigma - 1; i >= 0; i--) {
          if (cnt[i] > 0) modify(1, 1, n, pos, pos + cnt[i] - 1, i);
          pos += cnt[i];
        }
      }
    }
    getStr(1, 1, n);
    puts("");
  }
  return 0;
}