Ilya và các truy vấn (Ilya and Queries)

Nguồn: Codeforces

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

Đề bài

Cho một chuỗi $s$ chỉ gồm hai ký tự . và #.

Với mỗi truy vấn $[l,r]$, hãy đếm số vị trí $i$ thỏa

và hai ký tự kề nhau tại vị trí $i$ và $i+1$ giống nhau, tức là

Mỗi cặp ký tự kề nhau được xác định bởi vị trí bên trái của cặp. Chỉ những cặp nằm hoàn toàn bên trong đoạn $[l,r]$ mới được tính.

Input

• Dòng đầu chứa chuỗi $s$.
• Dòng thứ hai chứa số nguyên $m$, là số truy vấn.
• Mỗi trong $m$ 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ố cặp ký tự kề nhau giống nhau trong đoạn $[l,r]$.

Subtask

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

• $2\le |s|\le10^5$

• $s_i\in\{\texttt{.},\texttt{\#}\}$

• $1\le m\le10^5$

• $1\le l<r\le |s|$

• Subtask 1 — 20%: $|s|,m\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

......
4
3 4
2 3
1 6
2 6

Output

1
1
5
4

Giải thích

Chuỗi trong ví dụ là ......, vì vậy mọi cặp ký tự kề nhau đều giống nhau.

• Đoạn $[3,4]$ chứa đúng một cặp $(3,4)$, nên kết quả là $1$.
• Đoạn $[2,3]$ cũng chứa đúng một cặp, nên kết quả là $1$.
• Đoạn $[1,6]$ có $5$ cặp kề nhau: $(1,2),(2,3),(3,4),(4,5),(5,6)$.
• Đoạn $[2,6]$ có $4$ cặp kề nhau.