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;
int n, q;
char str[100007];
struct Node {
  int d[26];
  int D;
  bool sorted;
  bool Inc;
  void Insert(int v) {
    memset(d, 0, sizeof(d));
    D = d[v] = 1;
    sorted = false;
  }
  void Take(bool Left, int N) {
    D = N;
    if (Left) {
      for (int i = 0; i < 26; ++i) {
        if (N >= d[i])
          N -= d[i];
        else {
          d[i] = N;
          N = 0;
        }
      }
    } else {
      for (int i = 25; i >= 0; --i) {
        if (N >= d[i])
          N -= d[i];
        else {
          d[i] = N;
          N = 0;
        }
      }
    }
  }
  void Drop(bool Left, int N) {
    D = D - N;
    if (Left) {
      for (int i = 0; i < 26; ++i) {
        if (N >= d[i])
          N -= d[i], d[i] = 0;
        else {
          d[i] -= N;
          N = 0;
        }
      }
    } else {
      for (int i = 25; i >= 0; --i) {
        if (N >= d[i])
          N -= d[i], d[i] = 0;
        else {
          d[i] -= N;
          N = 0;
        }
      }
    }
  }
  Node operator+(const Node &B) const {
    Node C;
    C.sorted = false;
    for (int i = 0; i < 26; ++i) C.d[i] = d[i] + B.d[i];
    C.D = D + B.D;
    return C;
  }
  void show() {
    printf("D=%d\n", D);
    for (int i = 0; i < 26; ++i) {
      if (d[i]) printf("d[%d]=%d\n", i, d[i]);
    }
  }
} ST[100007 << 2];
void PushDown(int rt) {
  Node &L = ST[rt << 1], &R = ST[rt << 1 | 1];
  if (ST[rt].sorted) {
    int N = L.D;
    L = ST[rt];
    L.Take(ST[rt].Inc, N);
    N = R.D;
    R = ST[rt];
    R.Take(!ST[rt].Inc, N);
    ST[rt].sorted = false;
  }
}
void Build(int l, int r, int rt) {
  if (l == r) {
    ST[rt].Insert(str[l] - 'a');
    return;
  }
  int m = (l + r) >> 1;
  Build(l, m, rt << 1);
  Build(m + 1, r, rt << 1 | 1);
  ST[rt] = ST[rt << 1] + ST[rt << 1 | 1];
}
Node Query(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    return ST[rt];
  }
  PushDown(rt);
  int m = (l + r) >> 1;
  Node LANS, RANS;
  int X = 0;
  if (L <= m) LANS = Query(L, R, l, m, rt << 1), X += 1;
  if (R > m) RANS = Query(L, R, m + 1, r, rt << 1 | 1), X += 2;
  if (X == 1) return LANS;
  if (X == 2) return RANS;
  return LANS + RANS;
}
Node Sum;
void Update(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    int N = ST[rt].D;
    ST[rt] = Sum;
    ST[rt].Take(Sum.Inc, N);
    Sum.Drop(Sum.Inc, N);
    return;
  }
  int m = (l + r) >> 1;
  if (L <= m) Update(L, R, l, m, rt << 1);
  if (R > m) Update(L, R, m + 1, r, rt << 1 | 1);
  ST[rt] = ST[rt << 1] + ST[rt << 1 | 1];
}
void Sort(int L, int R, int Inc) {
  Sum = Query(L, R, 1, n, 1);
  Sum.sorted = true;
  Sum.Inc = Inc;
  Update(L, R, 1, n, 1);
}
void Down(int l, int r, int rt) {
  if (l == r) {
    for (int i = 0; i < 26; ++i) {
      if (ST[rt].d[i]) {
        str[l] = i + 'a';
        break;
      }
    }
    return;
  }
  PushDown(rt);
  int m = (l + r) >> 1;
  Down(l, m, rt << 1);
  Down(m + 1, r, rt << 1 | 1);
}
int main(void) {
  while (~scanf("%d%d", &n, &q)) {
    scanf("%s", str + 1);
    Build(1, n, 1);
    for (int i = 0; i < q; ++i) {
      int x, y, k;
      scanf("%d%d%d", &x, &y, &k);
      Sort(x, y, k);
    }
    Down(1, n, 1);
    printf("%s\n", str + 1);
  }
  return 0;
}