a798. Ilya and Queries ( 伊利亞和查詢 )

Content

Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam.

You've got string s = s₁s₂... s_n (n is the length of the string), consisting only of characters "." and "#" and m queries. Each query is described by a pair of integers l_i, r_i (1 ≤ l_i < r_i ≤ n). The answer to the query l_i, r_i is the number of such integers i (l_i ≤ i < r_i), that s_i = s_i + 1.

Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.

獅子伊利亞想幫助他所有的朋友通過考試。他們需要解決以下問題才能通過 IT 考試。

你有字符串 s = s₁s₂...s_n（n 是字符串的長度），只包含字符“。” 和 "#" 和 m 個查詢。每個查詢由一對整數 l_i, r_i (1 ≤ l_i< r_i ≤ n) 描述。查詢 l_i, r_i 的答案是此類整數 i (l_i ≤ i < r_i) 的數量，即 s_i = s_i + 1。

獅子伊利亞想幫助他的朋友，但有沒有人可以幫助他？幫助伊利亞，解決問題。

Input

The first line contains string s of length n (2 ≤ n ≤ 10⁵). It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer m (1 ≤ m ≤ 10⁵) — the number of queries. Each of the next m lines contains the description of the corresponding query. The i-th line contains integers l_i, r_i (1 ≤ l_i < r_i ≤ n).

第一行包含長度為 n (2 ≤ n ≤ 10⁵) 的字符串 s。保證給定的字符串只包含字符“.”。和 ”＃”。

下一行包含整數 m (1 ≤ m ≤ 10⁵) — 查詢數。接下來的 m 行中的每一行都包含相應查詢的描述。第 i 行包含整數 l_i, r_i (1 ≤ l_i < r_i ≤ n)。

Output

Print m integers — the answers to the queries in the order in which they are given in the input.

打印 m 個整數 — 按照輸入中給出的順序對查詢的答案。

Sample Input #1

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

Sample Output #1

Sample Input #2

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

Sample Output #2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (4%): 0.4s , <1K
公開測資點#1 (4%): 0.4s , <1K
公開測資點#2 (4%): 0.4s , <1K
公開測資點#3 (4%): 0.4s , <1K
公開測資點#4 (4%): 0.4s , <1K
公開測資點#5 (4%): 0.4s , <1M
公開測資點#6 (4%): 0.4s , <1M
公開測資點#7 (4%): 0.4s , <1M
公開測資點#8 (4%): 0.4s , <1M
公開測資點#9 (4%): 0.4s , <1M
公開測資點#10 (4%): 0.4s , <1M
公開測資點#11 (4%): 0.4s , <1M
公開測資點#12 (4%): 0.4s , <1M
公開測資點#13 (4%): 0.4s , <1M
公開測資點#14 (4%): 0.4s , <1M
公開測資點#15 (4%): 0.4s , <1M
公開測資點#16 (4%): 0.4s , <10M
公開測資點#17 (4%): 0.4s , <1M
公開測資點#18 (4%): 0.4s , <1M
公開測資點#19 (4%): 0.4s , <1M
公開測資點#20 (4%): 0.4s , <1M
公開測資點#21 (4%): 0.4s , <1M
公開測資點#22 (4%): 0.4s , <1M
公開測資點#23 (4%): 0.4s , <1M
公開測資點#24 (4%): 0.4s , <10M

Hint ：

Tags:

1100

出處:

Codeforces Round #186 [管理者：

lamkinun@gma... (Kinda Lam)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」