Nhiệm vụ đơn giản

Cho xâu $S$ độ dài $n$ chỉ gồm các chữ cái Latin thường, và $q$ truy vấn. Mỗi truy vấn gồm ba số nguyên $i$, $j$, $k$ và được xử lý ngay lập tức trên xâu hiện tại:

• Nếu $k=1$: sắp xếp đoạn con $S_i,S_{i+1},\dots ,S_j$ theo thứ tự không giảm.
• Nếu $k=0$: sắp xếp đoạn con $S_i,S_{i+1},\dots ,S_j$ theo thứ tự không tăng.

Các truy vấn được thực hiện lần lượt theo đúng thứ tự đã cho, truy vấn sau tác động lên kết quả của truy vấn trước. Hãy in ra xâu $S$ sau khi thực hiện xong tất cả $q$ truy vấn.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$: độ dài xâu và số truy vấn.
• Dòng thứ hai chứa xâu $S$ độ dài $n$, chỉ gồm chữ cái Latin thường.
• $q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $i$, $j$, $k$ mô tả một truy vấn.

Dữ liệu ra

In ra một dòng duy nhất là xâu $S$ sau khi thực hiện tất cả các truy vấn.

Ràng buộc

• $1\le n\le {10}^5$
• $0\le q\le 50000$
• $1\le i\le j\le n$
• $k\in \{0,1\}$

Ví dụ