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 các kí tự trên xâu trong đoạn từ l đến r sao cho sau khi sắp xếp thì xâu con trong đoạn từ l đến r sẽ 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ì bỏ qua truy vấn đó.

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. 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 (N, Q ≤ 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 các truy vấn (1 <= l <= r <= N)

Kết quả:

• Là xâu S sau Q truy vấn

Ví dụ:

XAU.INP          XAU.OUT
7 2              acacbab
aaccbba
1 3
5 7

XAU.INP          XAU.OUT
3 2              nam
nam
1 2
2 3 

Giải thích:

Trong ví dụ đầu tiên, sau truy vấn thứ nhất thì xâu S trở thành acacbba, sau truy vấn thứ hai thì xâu S trở thành acacbab

Trong ví dụ thứ hai, cả hai truy vấn đều không thể thực hiện nên xâu S không thay đổi

Subtask 1: N, Q ≤ ${10}^3$ (30% số điểm)

Subtask 2: Xâu S chỉ gồm kí tự a và b (30% số điểm)

Subtask 3: N, Q ≤ 20000 (40% số điểm)