CF390C.Inna and Candy Boxes

Inna loves sweets very much. She has n closed present boxes lines up in a row in front of her. Each of these boxes contains either a candy (Dima's work) or nothing (Sereja's work). Let's assume that the boxes are numbered from 1 to n, from left to right.

As the boxes are closed, Inna doesn't know which boxes contain candies and which boxes contain nothing. Inna chose number k and asked w questions to Dima to find that out. Each question is characterised by two integers l__i, r__i (1 ≤ l__i ≤ r__i ≤ n; r - l + 1 is divisible by k), the i-th question is: "Dima, is that true that among the boxes with numbers from l__i to r__i, inclusive, the candies lie only in boxes with numbers l__i + k - 1, l__i + 2_k_ - 1, l__i + 3_k_ - 1, ..., r__i?"

Dima hates to say "no" to Inna. That's why he wonders, what number of actions he will have to make for each question to make the answer to the question positive. In one action, Dima can either secretly take the candy from any box or put a candy to any box (Dima has infinitely many candies). Help Dima count the number of actions for each Inna's question.

Please note that Dima doesn't change the array during Inna's questions. That's why when you calculate the number of operations for the current question, please assume that the sequence of boxes didn't change.

伊娜非常喜欢糖果。她面前有一排共 $n$ 个关闭着的礼物盒，从左到右依次编号为 $1$ 到 $n$。每个盒子中要么装有一颗糖果（由迪马准备），要么为空（由谢尔盖准备）。

由于盒子是关闭的，伊娜并不知道哪些盒子里有糖果、哪些没有。于是她选定一个数 $k$，并向迪马提出了 $w$ 个问题，以探明真相。每个问题由两个整数 $l_i$、$r_i$ 描述（满足 $1 \le l_i \le r_i \le n$，且 $r_i - l_i + 1$ 能被 $k$ 整除）。第 $i$ 个问题为：“迪马，是否在编号从 $l_i$ 到 $r_i$（含端点）的所有盒子中，糖果仅出现在编号为 $l_i + k - 1,\, l_i + 2k - 1,\, l_i + 3k - 1,\, \dots,\, r_i$ 的盒子中？”

迪马很讨厌对伊娜说“不”。因此，他想知道：对于每个问题，他最少需要执行多少次操作，才能使该问题的答案为“是”。每次操作，迪马可以秘密地从任意一个盒子中取走一颗糖果，或者向任意一个盒子中放入一颗糖果（迪马拥有无限多的糖果）。请帮助迪马计算出对伊娜每个问题所需的最少操作次数。

请注意：在伊娜提问过程中，迪马不会实际修改盒子序列。因此，在计算当前问题所需的操作次数时，请假设盒子序列始终保持原始状态不变。

The first line of the input contains three integers n, k and w (1 ≤ k ≤ min(n, 10), 1 ≤ n, w ≤ 105). 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.

输入的第一行包含三个整数 $n$、$k$ 和 $w$（满足 $1 \leq k \leq \min(n, 10)$，$1 \leq n, w \leq 10^5$）。第二行包含 $n$ 个字符：若第 $i$ 个盒子中有一颗糖果，则该行的第 $i$ 个字符为 1，否则为 0。

接下来的 $w$ 行每行包含两个整数 $l_i$ 和 $r_i$（满足 $1 \leq l_i \leq r_i \leq n$），表示第 $i$ 个询问。保证 $r_i - l_i + 1$ 能被 $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.

对于每个问题，在单独一行中输出一个数字——Dima 为使该问题的答案变为正数所需的最少操作次数。

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.

对于第一问，你需要从第一个盒子中取出一颗糖，使答案为正数。因此答案是 1。

对于第二问，你需要从第一个盒子中取出一颗糖，从第五个盒子中取出一颗糖，并向第六个盒子中放入一颗糖。答案是 3。

对于第三问，你需要从第五个盒子中取出一颗糖，并将其放入第六个盒子中。答案是 2。