Bỏ qua đến nội dung

Truy vấn trên xâu

Mã bài: olp2024c2b Nhóm: Uncategorized Dạng bài: Undefined

Giới hạn thời gian
2,0 s
Giới hạn bộ nhớ
256 MB
Điểm
100một phần
Tỉ lệ AC
23,9%
Người giải
43

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

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ự A và B.
  • Subtask 3 - 30\% số điểm: Không có ràng buộc gì thêm

Bình luận