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 khoảng từ ~l~ đến ~r~ sao cho sau khi sắp xếp thì xâu con trong khoảng 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~.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~N~ và ~Q~ ~(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 các truy vấn ~(1 \le l \le r \le N)~.

Output

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

Scoring

Sample Input 1

7 2
aabcbaa
1 3
5 7

Sample Output 1

abacaba

Sample Input 2

3 2
abc
1 2
2 3

Sample Output 2

abc

Notes

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

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.