313B.md (1530B)
1 Source: https://codeforces.com/problemset/problem/313/B 2 3 B. Ilya and Queries 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam. 22 23 You've got string *s* = *s*1*s*2... *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. 24 25 Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem. 26 27 Input 28 29 The first line contains string *s* of length *n* (2 ≤ *n* ≤ 105). It is guaranteed that the given string only consists of characters "." and "#". 30 31 The next line contains integer *m* (1 ≤ *m* ≤ 105) — 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*). 32 33 Output 34 35 Print *m* integers — the answers to the queries in the order in which they are given in the input. 36 37 Examples 38 39 Input 40 41 ``` 42 ...... 43 4 44 3 4 45 2 3 46 1 6 47 2 6 48 ``` 49 50 Output 51 52 ``` 53 1 54 1 55 5 56 4 57 ``` 58 59 Input 60 61 ``` 62 #..### 63 5 64 1 3 65 5 6 66 1 5 67 3 6 68 3 4 69 ``` 70 71 Output 72 73 ``` 74 1 75 1 76 2 77 2 78 0 79 ```