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 N = 100100;
int n, q;
char s[N];
struct str {
  void bld() {
    for (char c = 'a'; c <= 'z'; c++) segtree[c - 'a'].bld(c);
  }
  void setRange(char ch, int u, int v, int l, int r) {
    if (r < l) return;
    segtree[ch - 'a'].setRange(0, l, r);
    if (v >= u) segtree[ch - 'a'].setRange(1, u, v);
  }
  vector<int> composition(int l, int r) {
    vector<int> ret;
    for (char c = 'a'; c <= 'z'; c++) {
      ret.emplace_back(segtree[c - 'a'].query(l, r));
    }
    return ret;
  }
  struct segment_tree {
    struct node {
      int sum = 0, tp;
      bool pu = 0;
    } tree[N << 2];
    void merge(node &nn, node &l, node &r) { nn.sum = l.sum + r.sum; }
    void push(int &x, int &lx, int &rx) {
      node &nn = tree[x];
      if (lx == rx) {
        if (nn.pu) {
          nn.sum = nn.tp;
          nn.pu = 0;
        }
        return;
      }
      if (nn.pu) {
        node &lc = tree[x + x];
        node &rc = tree[x + 1 + x];
        lc.pu = rc.pu = 1;
        lc.tp = rc.tp = nn.tp;
        nn.sum = (rx - lx + 1) * nn.tp;
        nn.pu = 0;
      }
    }
    void bld(char c, int x = 1, int lx = 1, int rx = n) {
      tree[x].pu = 0;
      if (lx == rx) {
        tree[x].sum = (s[lx] == c ? 1 : 0);
        return;
      }
      int mid = lx + rx >> 1;
      bld(c, x + x, lx, mid);
      bld(c, x + 1 + x, mid + 1, rx);
      merge(tree[x], tree[x + x], tree[x + 1 + x]);
    }
    int val, u, v;
    void upd(int x = 1, int lx = 1, int rx = n) {
      push(x, lx, rx);
      if (v < lx or u > rx) return;
      if (u <= lx and rx <= v) {
        tree[x].pu = 1;
        tree[x].tp = val;
        push(x, lx, rx);
        return;
      }
      int mid = lx + rx >> 1;
      upd(x + x, lx, mid);
      upd(x + 1 + x, mid + 1, rx);
      merge(tree[x], tree[x + x], tree[x + 1 + x]);
    }
    void setRange(int value, int l, int r) {
      val = value;
      u = l;
      v = r;
      upd();
    }
    int qry(int x = 1, int lx = 1, int rx = n) {
      push(x, lx, rx);
      if (v < lx or u > rx) return 0;
      if (u <= lx and rx <= v) return tree[x].sum;
      int mid = lx + rx >> 1;
      return qry(x + x, lx, mid) + qry(x + 1 + x, mid + 1, rx);
    }
    int query(int l, int r) {
      u = l;
      v = r;
      return qry();
    }
  } segtree[26];
} T;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  cin >> 1 + s;
  T.bld();
  int l, r, ty;
  while (q--) {
    cin >> l >> r >> ty;
    auto v = T.composition(l, r);
    if (ty == 1) {
      int packed = 0;
      for (char c = 'a'; c <= 'z'; c++) {
        int len = v[c - 'a'];
        T.setRange(c, l + packed, l + packed + len - 1, l, r);
        packed += len;
      }
    } else {
      int packed = 0;
      for (char c = 'z'; c >= 'a'; c--) {
        int len = v[c - 'a'];
        T.setRange(c, l + packed, l + packed + len - 1, l, r);
        packed += len;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    auto v = T.composition(i, i);
    char c = 'a' + (int)(max_element(v.begin(), v.end()) - v.begin());
    cout << c;
  }
  cout << '\n';
  return 0;
}