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

「雅礼集训 2018 Day2」操作

题目描述

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

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

输入格式

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

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

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

输出格式

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

样例

5 2 3
10101
1 3
1 4
1 5
2
2
-1

数据范围与提示

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

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