Truy vấn trên xâu

Cho xâu ~s~ độ dài ~n~ chỉ chứa các ký tự chữ cái in hoa từ A đến Z.

Thực hiện ~q~ truy vấn, mỗi truy vấn bao gồm hai số nguyên ~l~ và ~r~, yêu cầu in ra ký tự xuất hiện nhiều nhất trong đoạn ~[l,r]~, nếu có nhiều ký tự như vậy thì in ra ký tự có thứ tự từ điển nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n,q \le 5 \times 10^5)~.
• Dòng thứ hai chứa xâu ~s~ độ dài ~n~ chỉ gồm các ký tự chữ cái in hoa.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~ và ~r~ mô tả truy vấn ~(1 \le l \le r \le n)~.

Output

• Với mỗi truy vấn, in ra trên một dòng là ký tự xuất hiện nhiều nhất trong đoạn, nếu có nhiều ký tự như vậy thì in ra ký tự có thứ tự từ điển nhỏ nhất.

Examples

7 3
ABCCBBA
1 6
2 4
7 7

B
C
A

4 1
ABBA
1 4

A

Scoring

• Subtask ~1~ ~-~ ~38\%~ số điểm: ~n,q \le 4000~
• Subtask ~2~ ~-~ ~32\%~ số điểm: xâu ~s~ chỉ chứa hai ký tự A và B.
• Subtask ~3~ ~-~ ~30\%~ số điểm: Không có ràng buộc gì thêm