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 = 1000 * 100 + 20;
int data[4 * MAXN][30], flag[4 * MAXN][30], n, q;
string s;
void relax_flag(int c, int s, int e, int id) {
  int x = flag[id][c];
  if (x == -1) {
    return;
  }
  int mid = (s + e) / 2;
  flag[2 * id][c] = x;
  flag[2 * id + 1][c] = x;
  data[2 * id][c] = (mid - s) * x;
  data[2 * id + 1][c] = (e - mid) * x;
  flag[id][c] = -1;
}
void add(int l, int r, int c, int x, int s, int e, int id) {
  if (e <= l or r <= s) {
    return;
  }
  if (l <= s && e <= r) {
    data[id][c] = (e - s) * x;
    flag[id][c] = x;
    return;
  }
  relax_flag(c, s, e, id);
  int mid = (s + e) / 2;
  add(l, r, c, x, s, mid, 2 * id + 0);
  add(l, r, c, x, mid, e, 2 * id + 1);
  data[id][c] = data[2 * id][c] + data[2 * id + 1][c];
}
int get(int l, int r, int c, int s, int e, int id) {
  if (e <= l or r <= s) {
    return 0;
  }
  if (l <= s && e <= r) {
    return data[id][c];
  }
  int mid = (s + e) / 2;
  relax_flag(c, s, e, id);
  return get(l, r, c, s, mid, 2 * id) + get(l, r, c, mid, e, 2 * id + 1);
}
int main() {
  cin >> n >> q >> s;
  for (int i = 0; i < n; i++) {
    add(i, i + 1, s[i] - 'a', 1, 0, n, 1);
  }
  for (int i = 0; i < MAXN; i++) {
    for (int j = 0; j <= 26; j++) {
      flag[i][j] = -1;
    }
  }
  for (int i = 0; i < q; i++) {
    int l, r, type;
    cin >> l >> r >> type;
    l--;
    int ja = l;
    if (type == 1) {
      for (int i = 0; i < 26; i++) {
        int tedad = get(l, r, i, 0, n, 1);
        add(l, r, i, 0, 0, n, 1);
        add(ja, ja + tedad, i, 1, 0, n, 1);
        ja += tedad;
      }
    }
    if (type == 0) {
      for (int i = 25; i >= 0; i--) {
        int tedad = get(l, r, i, 0, n, 1);
        add(l, r, i, 0, 0, n, 1);
        add(ja, ja + tedad, i, 1, 0, n, 1);
        ja += tedad;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 26; j++) {
      if (get(i, i + 1, j, 0, n, 1) > 0) {
        cout << (char)(j + 'a');
      }
    }
  }
}