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 Maxn = 1e5 + 7;
int n, q;
string s;
int cnt[4 * Maxn][30], ted[30], c[4 * Maxn];
bool mark[4 * Maxn];
void pull(int node) {
  for (int i = 0; i < 26; i++)
    cnt[node][i] = cnt[2 * node][i] + cnt[2 * node + 1][i];
}
void push(int node, int l1, int l2) {
  if (!mark[node]) return;
  mark[node] = false;
  mark[2 * node] = mark[2 * node + 1] = true;
  for (int i = 0; i < 26; i++) cnt[2 * node][i] = cnt[2 * node + 1][i] = 0;
  c[2 * node] = c[2 * node + 1] = c[node];
  cnt[2 * node][c[node]] = l1;
  cnt[2 * node + 1][c[node]] = l2;
}
void add(int l, int r, int s, int e, int x, int node = 1) {
  if (r < s || e < l) return;
  if (e >= r && s <= l) {
    for (int i = 0; i < 26; i++) cnt[node][i] = 0;
    cnt[node][x] = r - l + 1;
    c[node] = x;
    mark[node] = true;
    return;
  }
  int mid = (l + r) / 2;
  push(node, mid - l + 1, r - mid);
  add(l, mid, s, e, x, 2 * node);
  add(mid + 1, r, s, e, x, 2 * node + 1);
  pull(node);
}
void Find(int l, int r, int s, int e, int node = 1) {
  if (l == s && r == e) {
    for (int i = 0; i < 26; i++) ted[i] += cnt[node][i];
    return;
  }
  if (mark[node]) {
    ted[c[node]] += e - s + 1;
    return;
  }
  int mid = (l + r) / 2;
  if (e <= mid)
    Find(l, mid, s, e, 2 * node);
  else if (mid < s)
    Find(mid + 1, r, s, e, 2 * node + 1);
  else
    Find(l, mid, s, mid, 2 * node), Find(mid + 1, r, mid + 1, e, 2 * node + 1);
}
void ans(int l, int r, int t) {
  for (int i = 0; i < 26 && r >= l; i++) {
    if (!ted[i]) continue;
    if (!t)
      add(0, n - 1, r - ted[i] + 1, r, i), r -= ted[i];
    else
      add(0, n - 1, l, l + ted[i] - 1, i), l += ted[i];
  }
}
int main() {
  cin >> n >> q;
  cin >> s;
  for (int i = 0; i < n; i++) add(0, n - 1, i, i, s[i] - 'a');
  while (q--) {
    int l, r, t;
    cin >> l >> r >> t;
    l--, r--;
    memset(ted, 0, sizeof ted);
    Find(0, n - 1, l, r);
    ans(l, r, t);
  }
  for (int i = 0; i < n; i++) {
    memset(ted, 0, sizeof ted);
    Find(0, n - 1, i, i);
    for (int i = 0; i < 26; i++)
      if (ted[i]) cout << (char)('a' + i);
  }
  cout << endl;
  return 0;
}