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 N = 1000 * 100 + 10;
int n, q;
int seg[26][4 * N], lazy[26][4 * N], b[26];
string a;
void build(int i, int v, int s, int e) {
  if (e - s <= 1) {
    char c = i + 'a';
    if (a[s] == c) {
      seg[i][v] = 1;
    }
    return;
  }
  int mid = (e + s) / 2;
  build(i, 2 * v, s, mid);
  build(i, 2 * v + 1, mid, e);
  seg[i][v] = seg[i][2 * v] + seg[i][2 * v + 1];
}
void shift(int i, int v, int s, int e) {
  if (lazy[i][v] == 0) return;
  int mid = (e + s) / 2;
  lazy[i][v * 2] = lazy[i][v];
  lazy[i][v * 2 + 1] = lazy[i][v];
  if (lazy[i][v] == 1) {
    seg[i][2 * v] = mid - s;
    seg[i][2 * v + 1] = e - mid;
  } else if (lazy[i][v] == 2) {
    seg[i][2 * v] = 0;
    seg[i][2 * v + 1] = 0;
  }
  lazy[i][v] = 0;
}
int get(int i, int l, int r, int v = 1, int s = 0, int e = n) {
  if (l <= s && e <= r + 1) return seg[i][v];
  int mid = (e + s) / 2;
  shift(i, v, s, e);
  if (r < mid)
    return get(i, l, r, v * 2, s, mid);
  else if (l >= mid)
    return get(i, l, r, v * 2 + 1, mid, e);
  else {
    return get(i, l, r, v * 2, s, mid) + get(i, l, r, v * 2 + 1, mid, e);
  }
}
void update(int val, int i, int l, int r, int v = 1, int s = 0, int e = n) {
  if (l <= s && e <= r + 1) {
    if (val == 1) {
      seg[i][v] = e - s;
      lazy[i][v] = 1;
    } else {
      seg[i][v] = 0;
      lazy[i][v] = 2;
    }
    return;
  }
  int mid = (s + e) / 2;
  shift(i, v, s, e);
  if (r < mid)
    update(val, i, l, r, v * 2, s, mid);
  else if (l >= mid)
    update(val, i, l, r, v * 2 + 1, mid, e);
  else {
    update(val, i, l, r, v * 2, s, mid);
    update(val, i, l, r, v * 2 + 1, mid, e);
  }
  seg[i][v] = seg[i][v * 2] + seg[i][v * 2 + 1];
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> q >> a;
  for (int i = 0; i < 26; i++) build(i, 1, 0, n);
  for (int i = 0; i < q; i++) {
    int x, y, k, st;
    cin >> x >> y >> k;
    x--;
    y--;
    for (int j = 0; j < 26; j++) {
      b[j] = get(j, x, y);
    }
    st = x;
    if (k == 1) {
      for (int j = 0; j < 26; j++) {
        if (b[j] == 0) continue;
        update(0, j, x, y);
        update(1, j, st, st + b[j] - 1);
        st += b[j];
      }
    } else {
      for (int j = 25; j >= 0; j--) {
        if (b[j] == 0) continue;
        update(0, j, x, y);
        update(1, j, st, st + b[j] - 1);
        st += b[j];
      }
    }
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 26; j++)
      if (get(j, i, i) == 1) {
        cout << ((char)('a' + j));
        break;
      }
  cout << '\n';
  return 0;
}