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;
char S[100005];
int cnt[256];
int lazy[(1 << 18) + 5][27];
int val[(1 << 18) + 5][27];
int n, q;
void init(int i = 1, int s = 1, int e = n) {
  if (s == e) {
    for (int k = 0; k < 26; k++) {
      val[i][k] = (k == S[s] - 'a');
      lazy[i][k] = -1;
    }
    return;
  } else {
    int l = (i << 1);
    int r = (i << 1) | 1;
    int m = (s + e) >> 1;
    init(l, s, m);
    init(r, m + 1, e);
    for (int k = 0; k < 26; k++) {
      val[i][k] = val[l][k] + val[r][k];
      lazy[i][k] = -1;
    }
  }
}
void propagate(int k, int i, int s, int e) {
  if (lazy[i][k] != -1) {
    if (s == e) {
      val[i][k] = lazy[i][k];
      lazy[i][k] = -1;
      return;
    } else {
      int l = (i << 1);
      int r = (i << 1) | 1;
      int m = (s + e) >> 1;
      val[i][k] = (e - s + 1) * lazy[i][k];
      val[l][k] = (m - s + 1) * lazy[i][k];
      val[r][k] = (e - (m + 1) + 1) * lazy[i][k];
      lazy[l][k] = lazy[i][k];
      lazy[r][k] = lazy[i][k];
      lazy[i][k] = -1;
      return;
    }
  }
}
void update(int k, int v, int x, int y, int i = 1, int s = 1, int e = n) {
  propagate(k, i, s, e);
  if (x <= s && e <= y) {
    lazy[i][k] = v;
    return;
  } else {
    int l = (i << 1);
    int r = (i << 1) | 1;
    int m = (s + e) >> 1;
    if (x > m) {
      update(k, v, x, y, r, m + 1, e);
    } else if (y <= m) {
      update(k, v, x, y, l, s, m);
    } else {
      update(k, v, x, y, r, m + 1, e);
      update(k, v, x, y, l, s, m);
    }
    propagate(k, l, s, m);
    propagate(k, r, m + 1, e);
    val[i][k] = val[l][k] + val[r][k];
  }
}
int query(int k, int x, int y, int i = 1, int s = 1, int e = n) {
  propagate(k, i, s, e);
  if (x <= s && e <= y) {
    return val[i][k];
  } else {
    int l = (i << 1);
    int r = (i << 1) | 1;
    int m = (s + e) >> 1;
    if (x > m) {
      return query(k, x, y, r, m + 1, e);
    } else if (y <= m) {
      return query(k, x, y, l, s, m);
    } else {
      return query(k, x, y, r, m + 1, e) + query(k, x, y, l, s, m);
    }
  }
}
void sortAsc(int x, int y) {
  for (char i = 'a'; i <= 'z'; i++) {
    cnt[i] = query(i - 'a', x, y);
  }
  int j = x;
  for (char i = 'a'; i <= 'z'; i++) {
    if (cnt[i] == 0) {
      continue;
    }
    update(i - 'a', 1, j, j + cnt[i] - 1);
    if (x <= j - 1) {
      update(i - 'a', 0, x, j - 1);
    }
    if (j + cnt[i] <= y) {
      update(i - 'a', 0, j + cnt[i], y);
    }
    j += cnt[i];
  }
  assert(j == y + 1);
}
void sortDesc(int x, int y) {
  for (char i = 'a'; i <= 'z'; i++) {
    cnt[i] = query(i - 'a', x, y);
  }
  int j = x;
  for (char i = 'z'; i >= 'a'; i--) {
    if (cnt[i] == 0) {
      continue;
    }
    update(i - 'a', 1, j, j + cnt[i] - 1);
    if (x <= j - 1) {
      update(i - 'a', 0, x, j - 1);
    }
    if (j + cnt[i] <= y) {
      update(i - 'a', 0, j + cnt[i], y);
    }
    j += cnt[i];
  }
  assert(j == y + 1);
}
int main() {
  scanf("%d%d", &n, &q);
  scanf(" %s", S + 1);
  init();
  while (q--) {
    int i, j, k;
    scanf("%d%d%d", &i, &j, &k);
    if (k == 0) {
      sortDesc(i, j);
    } else {
      sortAsc(i, j);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (char j = 'a'; j <= 'z'; j++) {
      if (query(j - 'a', i, i)) {
        putchar(j);
        break;
      }
    }
  }
  return 0;
}