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 MX = (1 << 17);
struct STR {
  int sum, flag;
  STR() { sum = flag = 0; }
} tree[26][MX * 4];
int st, en, dim;
bool cmd;
void flip(int x, int a, int b) {
  if (tree[dim][x].flag == -1) return;
  int lx = x * 2, la = a, lb = (a + b) / 2;
  if (tree[dim][x].flag)
    tree[dim][lx].sum = tree[dim][lx].flag = lb - la + 1;
  else
    tree[dim][lx].sum = tree[dim][lx].flag = 0;
  int rx = x * 2 + 1, ra = lb + 1, rb = b;
  if (tree[dim][x].flag)
    tree[dim][rx].sum = tree[dim][rx].flag = rb - ra + 1;
  else
    tree[dim][rx].sum = tree[dim][rx].flag = 0;
  tree[dim][x].flag = -1;
}
void update(int x, int a, int b) {
  if (st > b || en < a || st > en) return;
  if (a >= st && b <= en) {
    if (cmd)
      tree[dim][x].flag = tree[dim][x].sum = b - a + 1;
    else
      tree[dim][x].flag = tree[dim][x].sum = 0;
    return;
  }
  flip(x, a, b);
  update(x * 2, a, (a + b) / 2);
  update(x * 2 + 1, (a + b) / 2 + 1, b);
  tree[dim][x].sum = tree[dim][x * 2].sum + tree[dim][x * 2 + 1].sum;
}
int query(int x, int a, int b) {
  if (st > b || en < a || st > en) return 0;
  if (a >= st && b <= en) return tree[dim][x].sum;
  flip(x, a, b);
  return query(x * 2, a, (a + b) / 2) + query(x * 2 + 1, (a + b) / 2 + 1, b);
}
string str;
int n, Q, L, R, rev;
void work() {
  char ss = 'a', ee = 'z';
  if (rev) swap(ss, ee);
  int add = 0, cnt;
  while (1) {
    dim = ss - 'a';
    st = L, en = R;
    cnt = query(1, 1, n);
    cmd = 0;
    update(1, 1, n);
    st = L + add, en = L + add + cnt - 1;
    cmd = 1;
    update(1, 1, n);
    add += cnt;
    if (ss == ee) break;
    if (ss < ee)
      ss++;
    else
      ss--;
  }
  ss = 'a', ee = 'z';
  if (rev) swap(ss, ee);
  while (1) {
    dim = ss - 'a';
    st = L, en = R;
    cnt = query(1, 1, n);
    if (ss == ee) break;
    if (ss < ee)
      ss++;
    else
      ss--;
  }
}
string sol;
void DFS(int x, int a, int b) {
  if (a == b) {
    if (tree[dim][x].sum) sol[a - 1] = dim + 'a';
    return;
  }
  flip(x, a, b);
  DFS(x * 2, a, (a + b) / 2);
  DFS(x * 2 + 1, (a + b) / 2 + 1, b);
}
void out() {
  for (dim = 0; dim < 26; dim++) DFS(1, 1, n);
  cout << sol << endl;
}
int main() {
  cin >> n >> Q >> str;
  str = "#" + str;
  sol.resize(n);
  for (int j = 1; j <= n; j++) {
    dim = str[j] - 'a';
    cmd = 1;
    st = en = j;
    update(1, 1, n);
  }
  while (Q--) {
    scanf("%d %d %d", &L, &R, &rev);
    rev ^= 1;
    work();
  }
  out();
}