题目描述

有一个长度为 $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\times 10^6$, $m \leq 5\times 10^5$。

子任务 1 (10分)：$n, m \leq 500$
子任务 2 (20分)：$n, m \leq 5000$
子任务 3 (40分)：$n, m \leq 10^5$
子任务 4 (30分)：无特殊限制