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;
struct Node {
  int cnt, sgn;
};
int K, M;
char str[100005];
Node nodes[26][1 << 20] = {};
void syn(Node *root, int pos, int k) {
  int &sgn = root[pos].sgn;
  if (sgn == 0) return;
  if (k) {
    root[pos << 1].sgn = sgn;
    root[(pos << 1) | 1].sgn = sgn;
  }
  if (root[pos].sgn == 1)
    root[pos].cnt = 1 << k;
  else
    root[pos].cnt = 0;
  root[pos].sgn = 0;
}
int get(Node *root, int pos, int k) {
  syn(root, pos, k);
  return root[pos].cnt;
}
void sets(Node *root, int pos, int l, int r, int k, int sgn) {
  int pl = (pos << k) - M;
  int pr = ((pos + 1) << k) - 1 - M;
  l = max(l, pl);
  r = min(r, pr);
  if (l > r) return;
  syn(root, pos, k);
  if (pl == l && pr == r) {
    root[pos].sgn = sgn;
    return;
  }
  sets(root, pos << 1, l, r, k - 1, sgn);
  sets(root, (pos << 1) | 1, l, r, k - 1, sgn);
  int res = 0;
  res += get(root, pos << 1, k - 1);
  res += get(root, (pos << 1) | 1, k - 1);
  root[pos].cnt = res;
}
int get(Node *root, int pos, int l, int r, int k) {
  int pl = (pos << k) - M;
  int pr = ((pos + 1) << k) - 1 - M;
  l = max(l, pl);
  r = min(r, pr);
  if (l > r) return 0;
  syn(root, pos, k);
  if (pl == l && pr == r) {
    return root[pos].cnt;
  }
  int res = 0;
  res += get(root, pos << 1, l, r, k - 1);
  res += get(root, (pos << 1) | 1, l, r, k - 1);
  return res;
}
void init_tree(int n) {
  M = 1;
  K = 0;
  while (M < n) {
    ++K;
    M <<= 1;
  }
}
void mv(int l, int r, char c, int key) {
  c -= 'a';
  int cnt = get(nodes[c], 1, l, r, K);
  if (key) {
    sets(nodes[c], 1, l, l + cnt - 1, K, 1);
    sets(nodes[c], 1, l + cnt, r, K, 2);
  } else {
    sets(nodes[c], 1, l, r - cnt, K, 2);
    sets(nodes[c], 1, r - cnt + 1, r, K, 1);
  }
}
void mv(int l, int r, int key) {
  for (int i = 0; i < 26; ++i) mv(l, r, 'a' + i, key);
}
void add(Node *root, int pos) {
  pos += M;
  while (pos) {
    ++root[pos].cnt;
    pos >>= 1;
  }
}
void init(int n) {
  for (int i = 0; i < 26; ++i) {
    char c = i + 'a';
    for (int j = 0; j < n; ++j) {
      if (str[j] <= c) add(nodes[i], j);
    }
  }
}
int gbit(int k) {
  int cnt = 0;
  while (k < M) {
    k <<= 1;
    ++cnt;
  }
  return cnt;
}
void print(int n) {
  for (int i = 0; i < 26; ++i)
    for (int j = 0; j < M << 1; ++j)
      if (j) syn(nodes[i], j, gbit(j));
  for (int j = 0; j < n; ++j) {
    for (int i = 0; i < 26; ++i) {
      if (nodes[i][j + M].cnt) {
        str[j] = 'a' + i;
        break;
      }
    }
  }
}
void solve() {
  int n, q;
  cin >> n >> q;
  scanf("%s", str);
  init_tree(n);
  init(n);
  for (int i = 0; i < q; ++i) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    if (l == r) continue;
    mv(l - 1, r - 1, k);
  }
  print(n);
  printf("%s", str);
}
int main() {
  int n, q;
  solve();
  return 0;
}