Bạn được cho một chuỗi \(S\) có độ dài \(N\) bao gồm các ký tự \(A, C, G\) và \(T\). Trả lời các truy vấn \(Q\) sau:

Truy vấn thứ \(i (1 \leq i \leq Q)\): Bạn sẽ được cho hai số nguyên \(l_i\) và \(r_i\) \((1 \leq l_i < r_i \leq N)\). Xét chuỗi con của \(S\) bắt đầu từ chỉ số \(l_i\) và kết thúc ở chỉ số \(r_i\) (bao gồm cả hai). Trong chuỗi này, chuỗi con \(AC\) xuất hiện bao nhiêu lần?

Ghi chú

Một chuỗi con của một chuỗi \(T\) là một chuỗi thu được bằng cách loại bỏ không hoặc nhiều ký tự từ đầu và cuối của \(T\).

Ràng buộc

• \(2 \leq N \leq 10^5\)
• \(1 \leq Q \leq 10^5\)
• \(S\) là một chuỗi có độ dài \(N\).
• Mỗi ký tự trong \(S\) là \(A, C, G\) hoặc \(T\).
• \(1 \leq l_i < r_i \leq N\)

INPUT FORMAT

• Đầu vào được cung cấp từ Standard Input theo định dạng sau:

  N Q
  S
  l_1 r_1
  ...
  l_Q r_Q

OUTPUT FORMAT

• In ra \(Q\) dòng. Dòng thứ \(i\) chứa câu trả lời cho truy vấn thứ \(i\).

Ví dụ:

Input

8 3
ACACTACG
3 7
2 3
1 8

Output

2
0
3

Truy vấn thứ 1: chuỗi con của \(S\) bắt đầu từ chỉ số 3 và kết thúc ở chỉ số 7 là \(ACTAC\). Trong chuỗi này, \(AC\) xuất hiện hai lần.

Truy vấn thứ 2: chuỗi con của \(S\) bắt đầu từ chỉ số 2 và kết thúc ở chỉ số 3 là \(CA\). Trong chuỗi này, \(AC\) xuất hiện không lần nào.

Truy vấn thứ 3: chuỗi con của \(S\) bắt đầu từ chỉ số 1 và kết thúc ở chỉ số 8 là \(ACACTACG\). Trong chuỗi này, \(AC\) xuất hiện ba lần.

Giải thích ví dụ mẫu

Ví dụ:

• Input:

  8 3 ACACTACG 3 7 2 3 1 8

• Giải thích:

  • Truy vấn 1: Chuỗi con "ACTAC" có 2 lần "AC".
  • Truy vấn 2: Chuỗi con "CA" không có "AC".
  • Truy vấn 3: Chuỗi con "ACACTACG" có 3 lần "AC".
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House