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;
vector<int> v[26];
int main() {
  int n, q, l, r, k;
  string s;
  cin >> n >> q >> s;
  for (int i = 0; i < s.size(); i++) v[s[i] - 'a'].push_back(i);
  while (q--) {
    cin >> l >> r >> k;
    int cnt = --l;
    r--;
    if (k)
      for (int i = 0; i <= 26; ++i) {
        int ss = lower_bound(v[i].begin(), v[i].end(), l) - v[i].begin(),
            ff = upper_bound(v[i].begin(), v[i].end(), r) - v[i].begin();
        for (int j = ss; j < ff; j++) v[i][j] = cnt++;
      }
    else
      for (int i = 26; i >= 0; --i) {
        int ss = lower_bound(v[i].begin(), v[i].end(), l) - v[i].begin(),
            ff = upper_bound(v[i].begin(), v[i].end(), r) - v[i].begin();
        for (int j = ss; j < ff; ++j) v[i][j] = cnt++;
      }
  }
  for (int i = 0; i < 27; i++)
    for (int j = 0; j < v[i].size(); j++) s[v[i][j]] = char('a' + i);
  cout << s << endl;
  return 0;
}