Truy vấn trên xâu

View as PDF

Time limit: 2.0s , Memory limit: 256M , Points: 100 (partial)

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 lr, 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 nq (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 lr 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

Sample Input 1
7 3
ABCCBBA
1 6
2 4
7 7
Sample Output 1
B
C
A
Sample Input 2
4 1
ABBA
1 4
Sample Output 2
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ự AB.
  • Subtask 3 - 30\% số điểm: Không có ràng buộc gì thêm

Comments