CF390C Inna and Candy Boxes

Inna 非常喜欢甜食，她有 $n$ 个封闭的礼物盒排在她面前，每个盒子里要么装着糖果（Dima 的礼物），要么是空气（Sereja 的礼物），假设盒子的编号从左往右依次为 1 至 $n$ . 由于盒子是关闭的，Inna 不知道哪些盒子里有糖果，哪些盒子里是空气， Inna 选择了数字 $k$ 并问了 Dima $w$ 个问题以此来找出答案，每次询问带有两个数字 $l_i$ 与 $r_i$ （$1 \le l_i \le r_i \le n $ 且 $r-l+1$ 能被 $k$ 整除）。 对于第 $i$ 次询问，总为：“ Dima ，在编号为 $l_i$ 到 $r_i$ 的盒子中，是否仅仅只有编号为 $l_i+k-1$ , $l_i+2k-1$ , $l_i+3k-1$ , ... $r_i$ 的盒子中有糖果？” 因为Dima 不希望对 Inna 说“不”，因此他想知道，对于每次询问，他需要采取多少次行动才能使答案转为肯定回答。我们规定，在一次行动中，Dima 可以偷偷地从任意一个盒子里拿走糖果，也可以把糖果放进任意一个盒子里（由于 Dima 有无数个糖果，所以他可以随便放），请你帮助 Dima 计算，对于 Inna 的每次询问，需要采取多少次行动。 请注意，Dima 在 Inna 的询问期间不会改变数组。这也就是为什么当你计算当前问题的操作次数时，需要假设盒子的顺序没有改变。

第一行包含三个整数，$n$ ， $k$ 和 $w$ （$1 \le k \le min$（$ n , 10 $）, $1 \le n,w \le 10^5$） 第二行包含 $n$ 个数字，如果第 $i$ 个箱子中有糖果，则该行的第 $i$ 个字符为 $1$ ，否则为 $0$。 接下来 $w$ 行，每行两个整数 $l_i$ 与 $r_i$ （$1 \le l_i \le r_i \le n $ 且保证 $r-l+1$ 能被 $k$ 整除）。

对于每一次询问,输出一行一个数字，作为Dima肯定回答问题所需的最小操作数。

第一次询问,你需要从第一个盒子中取出一个糖果来作肯定回答，所以答案是 $1$。 第二次询问,你需要从第一盒中取出一个糖果,从第五盒中取出一个糖果,然后把一个糖果放在第六盒中，答案是 $3$。 第三次询问,你需要从第五个盒子里拿出一个糖果，再放一个在第六个盒子里，答案是 $2$。