← 返回题目列表

Codeforces · 313/B

B. 伊利亚和查询

中文机器翻译题面 查看原题

狮子伊利亚想要帮助他所有的朋友通过考试。他们需要解决以下问题才能通过 IT 考试。

你有字符串 s = s1s2... sn (n 是字符串的长度),仅由字符“.”组成。和“#”和 m 查询。每个查询由一对整数 li, ri (1 ≤ li < ri ≤ n) 描述。查询 li, ri 的答案是此类整数 i (li ≤ i < ri) 的数量,即 si = si + 1。

狮子伊利亚想要帮助他的朋友,但是有人可以帮助他吗?帮助伊利亚,解决问题。

输入

第一行包含长度为 n (2 ≤ n ≤ 105) 的字符串 s。保证给定的字符串仅由字符“.”组成。和 ”#”。

下一行包含整数 m (1 ≤ m ≤ 105) — 查询数。接下来的 m 行中的每一行都包含相应查询的描述。第 i 行包含整数 li, ri (1 ≤ li < ri ≤ n)。

输出

打印 m 个整数 — 按照输入中给出的顺序查询的答案。

示例

输入 #1

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

输出 #1

1
1
5
4

输入 #2

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

输出 #2

1
1
2
2
0