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, sigma = 26;
int pl[4 * maxn][sigma], sm[4 * maxn][sigma];
int tp[4 * maxn][sigma];
void push(int v, int l, int r, int c) {
  if (tp[v][c] == 1) {
    sm[v][c] = (r - l) * pl[v][c];
    if (r - l == 1) {
      tp[v][c] = 0;
      return;
    }
    tp[v << 1][c] = 1;
    tp[(v << 1) + 1][c] = 1;
    pl[v << 1][c] = pl[v][c];
    pl[(v << 1) + 1][c] = pl[v][c];
    tp[v][c] = 0;
  }
}
void add(int a, int b, int c, int v = 1, int l = 0, int r = maxn) {
  push(v, l, r, c);
  if (a <= l && r <= b) {
    tp[v][c] = 1;
    pl[v][c] = 1;
    push(v, l, r, c);
    return;
  }
  if (r <= a || b <= l) return;
  int m = (l + r) >> 1;
  add(a, b, c, v << 1, l, m);
  add(a, b, c, (v << 1) + 1, m, r);
  sm[v][c] = sm[v << 1][c] + sm[(v << 1) + 1][c];
}
int pop(int a, int b, int c, int v = 1, int l = 0, int r = maxn) {
  push(v, l, r, c);
  if (a <= l && r <= b) {
    int R = sm[v][c];
    tp[v][c] = 1;
    pl[v][c] = 0;
    push(v, l, r, c);
    return R;
  }
  if (r <= a || b <= l) return 0;
  int m = (l + r) >> 1;
  int ret = pop(a, b, c, v << 1, l, m) + pop(a, b, c, (v << 1) + 1, m, r);
  sm[v][c] = sm[v << 1][c] + sm[(v << 1) + 1][c];
  return ret;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  for (int i = 0; i < n; i++) add(i, i + 1, s[i] - 'a');
  while (q--) {
    int l, r, k;
    cin >> l >> r >> k;
    l--;
    int tl = l;
    for (int z = 0; z < sigma; z++) {
      int c = k ? z : sigma - z - 1;
      int cnt = pop(l, r, c);
      add(tl, tl + cnt, c);
      tl += cnt;
    }
  }
  for (int i = 0; i < n; i++)
    for (int c = 0; c < sigma; c++)
      if (pop(i, i + 1, c) == 1) cout << char(c + 'a');
  cout << endl;
  return 0;
}