Một nhiệm vụ đơn giản (A Simple Task)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho chuỗi chữ thường. Mỗi truy vấn $i,j,k$ sắp xếp chuỗi con $[i,j]$ tăng dần nếu $k=1$, giảm dần nếu $k=0$. In chuỗi cuối.

Input

Dòng đầu chứa $n,q$. Dòng thứ hai là chuỗi $S$ gồm $n$ chữ cái thường. Mỗi trong $q$ dòng sau chứa i j k: sắp xếp $S[i..j]$ tăng dần nếu $k=1$, giảm dần nếu $k=0$.

Output

In chuỗi cuối cùng sau tất cả thao tác.

Subtask

• Subtask 1 (20%): $n$ và số thao tác không vượt 30; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 2 (30%): $n$ và số thao tác không vượt 3000; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

• $1\le n\le10^5$

• $0\le q\le50000$

• Chuỗi chỉ gồm chữ thường a..z.

Ví dụ

Input

10 1
agjucbvdfk
1 10 1

Output

abcdfgjkuv

Giải thích

Toàn bộ chuỗi được sắp tăng dần, thu được abcdfgjkuv.