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;
int n;
char s[100514 * 2];
int tag[100514];
int cnt[100514][26];
int acnt[26];
typedef struct {
  int id, l, r;
} ele;
vector<ele> ae;
int cmp(char a, char b) { return a > b; }
void mdfs(int id, int l, int r, int k) {
  if (tag[id] != -1) return;
  l += id * 512;
  r += id * 512 + 1;
  if (k == 1) {
    sort(s + l, s + r);
  } else if (k == 0) {
    sort(s + l, s + r, cmp);
  }
}
void cnts(int id, int l, int r) {
  if (tag[id] != -1) {
    for (int i = 0; i < (512); i++) s[i + id * 512] = tag[id];
    acnt[tag[id]] += r - l + 1;
    cnt[id][tag[id]] -= r - l + 1;
    tag[id] = -1;
    return;
  }
  l += id * 512;
  r += id * 512;
  for (int i = l; i <= r; i++) {
    acnt[s[i]]++;
    cnt[id][s[i]]--;
  }
}
void workcnt(int ld, int rd, int l, int r) {
  for (int i = 0; i < (26); i++) acnt[i] = 0;
  ae.clear();
  ae.push_back((ele){ld, l % 512, 512 - 1});
  cnts(ld, l % 512, 512 - 1);
  for (int i = ld + 1; i < rd; i++) {
    ae.push_back((ele){i, 0, 512 - 1});
    for (int j = 0; j < (26); j++) {
      acnt[j] += cnt[i][j];
      cnt[i][j] = 0;
    }
  }
  ae.push_back((ele){rd, 0, r % 512});
  cnts(rd, 0, r % 512);
}
void mdf1(int ld, int rd, int l, int r) {
  workcnt(ld, rd, l, r);
  int c = 0;
  reverse((ae).begin(), (ae).end());
  for (; ((int)ae.size());) {
    ele it = ae.back();
    ae.pop_back();
    int id = it.id;
    for (; c < 26 && acnt[c] == 0; c++)
      ;
    if (acnt[c] >= 512 && it.r == 512 - 1 && it.l == 0) {
      tag[id] = c;
      cnt[id][c] = 512;
      acnt[c] -= 512;
    } else {
      tag[id] = -1;
      int i = id * 512 + it.l;
      for (; acnt[c] && i <= id * 512 + it.r;) {
        s[i] = c;
        cnt[id][c]++;
        acnt[c]--;
        i++;
      }
      if (i <= id * 512 + it.r) {
        it.l = i - id * 512;
        ae.push_back(it);
      }
    }
  }
}
void mdf0(int ld, int rd, int l, int r) {
  workcnt(ld, rd, l, r);
  int c = 0;
  for (; ((int)ae.size());) {
    ele it = ae.back();
    ae.pop_back();
    int id = it.id;
    for (; c < 26 && acnt[c] == 0; c++)
      ;
    if (acnt[c] >= 512 && it.r == 512 - 1 && it.l == 0) {
      tag[id] = c;
      cnt[id][c] = 512;
      acnt[c] -= 512;
    } else {
      tag[id] = -1;
      int i = id * 512 + it.r;
      for (; acnt[c] && i >= id * 512 + it.l;) {
        s[i] = c;
        cnt[id][c]++;
        acnt[c]--;
        i--;
      }
      if (i >= id * 512 + it.l) {
        it.r = i - id * 512;
        ae.push_back(it);
      }
    }
  }
}
int sol(int uuu) {
  int q;
  if (scanf("%d %d", &(n), &(q)) == EOF) return 0;
  scanf("%s", s);
  for (int i = 0; i < n; i++) s[i] -= 'a';
  int nn = n / 512 + (n % 512 != 0);
  for (int i = 0; i < (nn); i++) {
    tag[i] = -1;
    for (int j = 0; j < (26); j++) cnt[i][j] = 0;
    for (int j = i * 512; j < min((i + 1) * 512, n); j++) {
      cnt[i][s[j]]++;
    }
  }
  for (int qi = 0; qi < (q); qi++) {
    int l, r, k;
    scanf("%d %d", &(l), &(r));
    scanf("%d", &(k));
    l--;
    r--;
    int ld = l / 512, rd = r / 512;
    if (ld == rd) {
      mdfs(ld, l % 512, r % 512, k);
    } else if (k) {
      mdf1(ld, rd, l, r);
    } else {
      mdf0(ld, rd, l, r);
    }
  }
  for (int i = 0; i < (nn); i++) cnts(i, 0, 0);
  for (int i = 0; i < (n); i++) s[i] += 'a';
  puts(s);
  return 1;
}
int main() {
  while (sol(0))
    ;
  return 0;
}