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, q;
string s;
char c;
class Node {
 public:
  int low;
  int high;
  int count;
  Node() {}
  Node(int low, int high, int count) {
    this->high = high;
    this->low = low;
    this->count = count;
  }
};
Node** arr = new Node*[26];
int size;
Node construct(Node* arr, int l, int h, int root) {
  if (l == h) {
    if (s[h] == c)
      arr[root] = Node(l, h, 1);
    else
      arr[root] = Node(l, h, 0);
    return arr[root];
  }
  int mid = l + (h - l) / 2;
  Node nl = construct(arr, l, mid, 2 * root + 1);
  Node nr = construct(arr, mid + 1, h, 2 * root + 2);
  arr[root] = Node(l, h, nl.count + nr.count);
  return arr[root];
}
int full(Node* arr, int i) { return arr[i].high - arr[i].low + 1; }
int getCount(Node* arr, int ind, int l, int h) {
  if (arr[ind].low != arr[ind].high && full(arr, ind) == arr[ind].count) {
    arr[2 * ind + 1].count = full(arr, 2 * ind + 1);
    arr[2 * ind + 2].count = full(arr, 2 * ind + 2);
  }
  if (arr[ind].count == 0)
    return 0;
  else if (l <= arr[ind].low && arr[ind].high <= h)
    return arr[ind].count;
  else if (l > arr[ind].high || arr[ind].low > h)
    return 0;
  else
    return getCount(arr, 2 * ind + 1, l, h) + getCount(arr, 2 * ind + 2, l, h);
}
void fix(Node* arr, int ind) {
  if (ind == 0)
    return;
  else {
    int par = (ind - 1) / 2;
    arr[par].count = arr[2 * par + 1].count + arr[2 * par + 2].count;
    fix(arr, par);
  }
}
void setCount(Node* arr, int ind, int l, int h) {
  if (l <= arr[ind].low && arr[ind].high <= h) {
    arr[ind].count = full(arr, ind);
    fix(arr, ind);
  } else if (l > arr[ind].high || arr[ind].low > h)
    return;
  else {
    if (arr[ind].low != arr[ind].high && full(arr, ind) == arr[ind].count) {
      arr[2 * ind + 1].count = full(arr, 2 * ind + 1);
      arr[2 * ind + 2].count = full(arr, 2 * ind + 2);
    }
    if (arr[ind].low != arr[ind].high && arr[ind].count == 0) {
      arr[2 * ind + 1].count = 0;
      arr[2 * ind + 2].count = 0;
    }
    setCount(arr, 2 * ind + 1, l, h);
    setCount(arr, 2 * ind + 2, l, h);
  }
}
void zeroCount(Node* arr, int ind, int l, int h) {
  if (l <= arr[ind].low && arr[ind].high <= h) {
    arr[ind].count = 0;
    fix(arr, ind);
  } else if (l > arr[ind].high || arr[ind].low > h)
    return;
  else {
    if (arr[ind].low != arr[ind].high && full(arr, ind) == arr[ind].count) {
      arr[2 * ind + 1].count = full(arr, 2 * ind + 1);
      arr[2 * ind + 2].count = full(arr, 2 * ind + 2);
    }
    if (arr[ind].low != arr[ind].high && arr[ind].count == 0) {
      arr[2 * ind + 1].count = 0;
      arr[2 * ind + 2].count = 0;
    }
    zeroCount(arr, 2 * ind + 1, l, h);
    zeroCount(arr, 2 * ind + 2, l, h);
  }
}
int main() {
  cin >> n >> q;
  cin >> s;
  int temp = n - 1;
  size = 1;
  while (temp > 0) {
    temp /= 2;
    size *= 2;
  }
  size = 2 * size - 1;
  for (int i = 0; i < 26; i++) {
    arr[i] = new Node[size];
    for (int j = 0; j < size; j++) arr[i][j] = Node(0, 0, 0);
  }
  for (int i = 0; i < 26; i++) {
    c = 'a' + (char)i;
    construct(arr[i], 0, n - 1, 0);
  }
  int l, r, k;
  for (int t = 0; t < q; t++) {
    cin >> l >> r >> k;
    l--;
    r--;
    if (k == 1) {
      int loc = l;
      for (int i = 0; i < 26; i++) {
        int countI = getCount(arr[i], 0, l, r);
        if (loc + countI - 1 >= loc) setCount(arr[i], 0, loc, loc + countI - 1);
        if (loc - 1 >= l) zeroCount(arr[i], 0, l, loc - 1);
        if (r >= loc + countI) zeroCount(arr[i], 0, loc + countI, r);
        loc += countI;
      }
    } else {
      int loc = r;
      for (int i = 0; i < 26; i++) {
        int countI = getCount(arr[i], 0, l, r);
        if (loc >= loc - countI + 1) setCount(arr[i], 0, loc - countI + 1, loc);
        if (r >= loc + 1) zeroCount(arr[i], 0, loc + 1, r);
        if (loc - countI >= l) zeroCount(arr[i], 0, l, loc - countI);
        loc -= countI;
      }
    }
  }
  for (int i = 0; i < 26; i++) {
    for (unsigned int j = 0; j < s.length(); j++) {
      if (getCount(arr[i], 0, j, j) == 1) s[j] = 'a' + (char)i;
    }
  }
  cout << s << endl;
  return 0;
}