Xâu con đối xứng

Cho xâu $S$ gồm $N$ chữ cái in thường và $Q$ truy vấn. Mỗi truy vấn gồm $2$ số nguyên $l,r$. Với mỗi truy vấn, bạn cần sắp xếp lại các kí tự của xâu trong khoảng từ vị trí $l$ đến vị trí $r$ sao cho sau khi sắp xếp, xâu con từ $l$ đến $r$ là một xâu palindrome có thứ tự từ điển nhỏ nhất có thể; nếu không sắp xếp được thành xâu palindrome thì bỏ qua truy vấn đó (xâu giữ nguyên). Các truy vấn được thực hiện lần lượt theo thứ tự, mỗi truy vấn áp dụng lên xâu đã thay đổi bởi các truy vấn trước. Xâu palindrome là xâu khi đọc từ trái qua phải cũng giống như đọc từ phải qua trái.

Yêu cầu: In ra xâu $S$ sau $Q$ truy vấn.

Lưu ý: vị trí các kí tự trong xâu $S$ được đánh số từ $1$ đến $N$.

Dữ liệu vào

• Dòng đầu tiên gồm $2$ số nguyên $N$ và $Q$ ($1\le N,Q\le 20000$).
• Dòng thứ hai gồm $N$ kí tự biểu diễn xâu $S$.
• $Q$ dòng tiếp theo, mỗi dòng gồm $2$ số nguyên $l,r$ biểu diễn một truy vấn ($1\le l\le r\le N$).

Dữ liệu ra

In ra xâu $S$ sau $Q$ truy vấn.

Ràng buộc

• $1\le N,Q\le 20000$.
• $S$ chỉ gồm chữ cái tiếng Anh in thường.
• $1\le l\le r\le N$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $N,Q\le {10}^3$.
• Subtask 2 ($30\%$ số điểm): xâu $S$ chỉ gồm kí tự a và b.
• Subtask 3 ($40\%$ số điểm): $N,Q\le 20000$.

Mỗi subtask được chấm theo nhóm: chỉ được điểm của subtask khi đúng mọi test thuộc subtask đó.

Ví dụ