← 返回题目列表

Codeforces · 390/C

C. Inna 和糖果盒

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

Inna非常喜欢甜食。她面前排成一排,有n个关着的礼物盒子。每个盒子要么装有糖果(迪玛的作品),要么什么也没有(塞雷贾的作品)。假设盒子从左到右编号为 1 到 n。

由于盒子是关闭的,Inna 不知道哪些盒子里有糖果,哪些盒子里什么也没有。 Inna 选择了 k 并向 Dima 提出了 w 个问题来找出答案。每个问题都以两个整数 li, ri 为特征(1 ≤ li ≤ ri ≤ n;r - l + 1 可被 k 整除),第 i 个问题是:“迪玛,在编号为 li 到 ri 的盒子中,糖果只位于编号为 li + k - 1, li + 2k - 1, li + 3k - 1, ..., ri 的盒子里吗?”

迪玛讨厌对伊娜说“不”。这就是为什么他想知道,他必须对每个问题采取多少行动才能得到积极的答案。在一个动作中,迪玛可以偷偷地从任何盒子里拿走糖果,或者把一颗糖果放入任何盒子里(迪玛有无限多的糖果)。帮助 Dima 计算每个 Inna 问题的动作数量。

请注意,Dima 在 Inna 提问期间不会更改数组。这就是为什么当您计算当前问题的操作数时,请假设框的顺序没有改变。

输入

输入的第一行包含三个整数 n、k 和 w (1 ≤ k ≤ min(n, 10)、1 ≤ n、w ≤ 105)。第二行包含n个字符。如果第 i 个盒子包含糖果,则该行的第 i 个字符等于 1,否则等于 0。

以下 w 行均包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ n) — 第 i 个问题的描述。保证 ri - li + 1 能被 k 整除。

输出

对于每个问题,在一行上打印一个数字 - Dima 需要使问题得到肯定答案所需的最少运算次数。

示例

输入 #1

10 3 3
1010100011
1 3
1 6
4 9

输出 #1

1
3
2

注意

对于第一个问题,你需要从第一个盒子里取出一颗糖果才能得到正确的答案。所以答案是1。

第二题,你需要从第一个盒子里拿一颗糖果,从第五个盒子里拿一颗糖果,然后把一颗糖果放到第六个盒子里。答案是3。

第三题,你需要从第五个盒子里取出一颗糖果,放到第六个盒子里。答案是2。