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 = 100 * 1000 + 3, CMX = 'z' - 'a' + 1;
int n, m, seg[CMX + 3][MAXN << 2], lazy[CMX + 3][MAXN << 2], a[CMX];
string s;
void add(int id, int l, int r, int v = 1, int st = 0, int ed = MAXN) {
  if (l >= ed || r <= st) return;
  if (l <= st && ed <= r) return seg[id][v] = ed - st, lazy[id][v] = 1, void(0);
  int mid = (st + ed) >> 1;
  if (lazy[id][v] != 0) {
    seg[id][v << 1] = lazy[id][v] == 1 ? mid - st : 0,
                 seg[id][(v << 1) | 1] = lazy[id][v] == 1 ? ed - mid : 0;
    lazy[id][v << 1] = lazy[id][v], lazy[id][(v << 1) | 1] = lazy[id][v];
    lazy[id][v] = 0;
  }
  add(id, l, r, v << 1, st, mid), add(id, l, r, (v << 1) | 1, mid, ed);
  seg[id][v] = seg[id][v << 1] + seg[id][(v << 1) | 1];
}
void rest(int id, int l, int r, int v = 1, int st = 0, int ed = MAXN) {
  if (l >= ed || r <= st) return;
  if (l <= st && ed <= r) return seg[id][v] = 0, lazy[id][v] = -1, void(0);
  int mid = (st + ed) >> 1;
  if (lazy[id][v] != 0) {
    seg[id][v << 1] = lazy[id][v] == 1 ? mid - st : 0,
                 seg[id][(v << 1) | 1] = lazy[id][v] == 1 ? ed - mid : 0;
    lazy[id][v << 1] = lazy[id][v], lazy[id][(v << 1) | 1] = lazy[id][v];
    lazy[id][v] = 0;
  }
  rest(id, l, r, v << 1, st, mid), rest(id, l, r, (v << 1) | 1, mid, ed);
  seg[id][v] = seg[id][v << 1] + seg[id][(v << 1) | 1];
}
int get(int id, int l, int r, int v = 1, int st = 0, int ed = MAXN) {
  if (l >= ed || r <= st || seg[id][v] == 0) return 0;
  if (l <= st && ed <= r) return seg[id][v];
  int mid = (st + ed) >> 1;
  if (lazy[id][v] != 0) {
    seg[id][v << 1] = lazy[id][v] == 1 ? mid - st : 0,
                 seg[id][(v << 1) | 1] = lazy[id][v] == 1 ? ed - mid : 0;
    lazy[id][v << 1] = lazy[id][v], lazy[id][(v << 1) | 1] = lazy[id][v];
    lazy[id][v] = 0;
  }
  return get(id, l, r, v << 1, st, mid) + get(id, l, r, (v << 1) | 1, mid, ed);
}
void build(int id, int v = 1, int st = 0, int ed = MAXN) {
  if (st >= n) return;
  if (ed - st == 1) return seg[id][v] = (s[st] == 'a' + id ? 1 : 0), void(0);
  int mid = (st + ed) >> 1;
  build(id, v << 1, st, mid), build(id, (v << 1) | 1, mid, ed);
  seg[id][v] = seg[id][v << 1] + seg[id][(v << 1) | 1];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> m >> s;
  for (int i = 0; i < CMX; i++) build(i);
  for (int i = 0; i < m; i++) {
    int l, r, sm = 0, k;
    cin >> l >> r >> k;
    l--;
    for (int i = 0; i < CMX; i++) (a[i] = get(i, l, r));
    for (int i = 0; i < CMX; i++) rest(i, l, r);
    if (k == 1)
      for (int i = 0; i < CMX; i++) add(i, l + sm, l + sm + a[i]), sm += a[i];
    else
      for (int i = CMX - 1; ~i; i--) add(i, l + sm, l + sm + a[i]), sm += a[i];
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < CMX; j++)
      if (get(j, i, i + 1)) {
        cout << (char)(j + 'a');
        break;
      }
  return 0;
}