Đoạn ký hiệu ổn định

Bối cảnh và bài toán

Một chuỗi trạng thái chỉ gồm . và #. Với mỗi truy vấn [l,r], hệ thống cần đếm số vị trí i trong đoạn sao cho trạng thái tại i giống trạng thái tại i+1. Chuỗi không thay đổi giữa các truy vấn.

Yêu cầu

Trả lời tất cả truy vấn một cách hiệu quả.

Input

• Dòng 1 chứa chuỗi s.
• Dòng 2 chứa q.
• q dòng tiếp theo chứa l r.

Output

In số cặp kề bằng nhau trong từng đoạn truy vấn.

Ràng buộc

• 2 <= \|s\| <= 10^5
• 1 <= q <= 10^5
• 1 <= l < r <= \|s\|

Chấm điểm

Ví dụ 1

Input

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

Output

1
1
5
4

Giải thích. Mỗi cặp ký tự kề đều giống nhau.

Ví dụ 2

Input

#..###
5
1 3
5 6
1 5
3 6
3 4

Output

1
1
2
2
0

Giải thích. Ta chỉ đếm các vị trí i sao cho s[i]=s[i+1] nằm hoàn toàn trong đoạn.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces 313B – Ilya and Queries.