#6500. 「雅礼集训 2018 Day2」操作

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一个长度为 n 01 序列, m 次询问,每次询问给出一个区间,你可以进行若干次操作,每次选择这个区间的一个长度为 k 的子区间,并将这个子区间的所有 01 取反,求至少需要几次操作才能将这个区间内的所有元素变成 0

请注意,每次询问都是独立的,你在一个询问中进行的操作不会影响另一个询问。

输入格式

第一行包括三个正整数 n, k, m

第二行给出一个长度为 n 01 串,表示这个序列。

接下来 m 行,每行两个正整数,表示询问的区间。

输出格式

对每个询问输出一个整数表示答案,如果不能将区间内所有元素都变为 0 ,输出 -1

样例

样例输入 1

5 2 3
10101
1 3
1 4
1 5

样例输出 1

2
2
-1

数据范围与提示

对于全部数据, k \leq n \leq 2×10^6, m \leq 5×10^5

  • 子任务 \rm 1(points:10) n, m \leq 500
  • 子任务 \rm 2(points:20) n, m \leq 5000
  • 子任务 \rm 3(points:40) n, m \leq 10^5
  • 子任务 \rm 4(points:30) :无特殊限制