Đếm chuỗi AC (GeT AC)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho chuỗi ADN $S$ có độ dài $N$, mỗi ký tự thuộc một trong bốn loại A, C, G, T.

Một lần xuất hiện của chuỗi AC được xác định bởi hai vị trí kề nhau $i$ và $i+1$ sao cho

Với mỗi truy vấn $[l,r]$, hãy đếm số lần AC xuất hiện hoàn toàn bên trong đoạn $S_lS_{l+1}\ldots S_r$.

Input

• Dòng đầu chứa hai số nguyên $N,Q$.
• Dòng thứ hai chứa chuỗi $S$ có độ dài $N$.
• Mỗi trong $Q$ dòng tiếp theo chứa hai số nguyên $l,r$.

Output

Với mỗi truy vấn, in trên một dòng số lần chuỗi AC xuất hiện trong đoạn được hỏi.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $2\le N\le10^5$

• $1\le Q\le10^5$

• $S_i\in\{A,C,G,T\}$

• $1\le l<r\le N$

• Subtask 1 — 20%: $N,Q\le40$

• Subtask 2 — 30%: Mọi truy vấn đều có $l=1$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

8 3
ACACTACG
3 7
2 3
1 8

Output

2
0
3

Giải thích

Chuỗi là ACACTACG. Các lần xuất hiện của AC bắt đầu tại vị trí $1$, $3$ và $6$.

• Trong đoạn $[3,7]$, có hai lần xuất hiện: tại $(3,4)$ và $(6,7)$.
• Trong đoạn $[2,3]$, chuỗi con là CA, nên không có AC.
• Trong đoạn $[1,8]$, cả ba lần xuất hiện đều nằm hoàn toàn trong đoạn.