Given a string $S$ of length $n$ consisting of lowercase letters, there are $q$ queries of the form $(l, r, k)$. If $k$ is equal to $1$, sort the substring $S[l...r]$ in non-decreasing order; otherwise, if $k$ is equal to $0$, sort it in non-increasing order.
### Input
- The first line contains two integers $n, q$.
- The second line contains the string $S$.
- The next $q$ lines each contain three integers $l, r, k$.
### Output
- Print the string $S$ after performing the $q$ queries.
### Constraints
- $1 \le n \le 10^5$, $1 \le q \le 5 \times 10^4$.
### Example
Input:
```
7 4
pmyyrgz
2 5 1
4 5 0
5 6 1
2 4 1
```
Output:
```
pmrygyz
```
