A9292 | Inna and Candy Boxes

The first line of the input contains three integers $n$ , $k$ and $w$ $(1<=k<=min(n,10),1<=n,w<=10^{5})$ . The second line contains $n$ characters. If the $i$ -th box contains a candy, the $i$ -th character of the line equals 1, otherwise it equals 0.

Each of the following $w$ lines contains two integers $l_{i}$ and $r_{i}$ $(1<=l_{i}<=r_{i}<=n)$ — the description of the $i$ -th question. It is guaranteed that $r_{i}-l_{i}+1$ is divisible by $k$ .

For each question, print a single number on a single line — the minimum number of operations Dima needs to make the answer to the question positive.

For the first question, you need to take a candy from the first box to make the answer positive. So the answer is 1.

For the second question, you need to take a candy from the first box, take a candy from the fifth box and put a candy to the sixth box. The answer is 3.

For the third question, you need to take a candy from the fifth box and put it to the sixth box. The answer is 2.