题目描述

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

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

输入格式

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

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

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

输出格式

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

样例

5 2 3
10101
1 3
1 4
1 5

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)$：无特殊限制