「KDOI-03」序列变换

给定一个长度为 $n$ 的 $\tt01$ 序列 $a$ 和 $q$ 次询问，询问参数 $k$。 每次询问给定 $L,R$，其中 $1\leq L\leq R\leq n$，你可以进行如下操作： + 选择一个下标 $L<i\le R$； + 将 $a_{i-1}$ 赋值为 $a_{i-1}\oplus a_i$，$a_{i+1}$ 赋值为 $a_{i+1}\oplus a_i$。如果 $i=n$，则不对 $a_{i+1}$ 作出改变。其中 $\oplus$ 表示按位异或运算。 求使得 $[L,R]$ 区间内**至多**有 $k$ 个 $\tt1$ 的最小操作次数。询问之间相互独立，也就是说，每次询问后重置为初始序列。

从标准输入读入数据。 第一行包含三个正整数 $n,k,q$。 第二行包含 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$。 接下来 $q$ 行，每行包含两个正整数 $L,R$，表示一次询问。

输出到标准输出。 输出共 $q$ 行，每行包含一个整数，表示答案。

5 1 2
1 1 1 0 1
2 3
1 3

1
1

20 3 22
0 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 0 1 
12 15
1 6
5 10
2 5
9 18
6 17
2 13
4 16
2 8
9 19
10 15
7 15
1 3
14 18
6 17
12 14
7 16
14 18
11 12
3 5
3 6
3 15

0
1
0
0
0
6
3
5
1
0
0
0
0
0
6
0
0
0
0
0
1
3

**【样例 1 解释】** 如图，用绿色代表 $\tt0$，红色代表 $\tt1$，初始序列如下：  对于第 $1$ 次询问，选择 $i=3$，则序列变为下图：  对于第 $2$ 次询问，选择 $i=2$，则序列变为下图：  **【样例 2 解释】** 对于第 $1$ 次询问，由于 $a_{12},a_{13},a_{14},a_{15}$ 中只有 $2$ 个 $\tt1$，所以不需要进行任何操作。 对于第 $6$ 次询问，可以依次选择 $i=\{7,8,9,10,11,12\}$。 **【样例 3】** 见选手文件中的 `control/control3.in` 与 `control/control3.ans`。 此样例满足测试点 $7\sim10$ 的限制。 **【样例 4】** 见选手文件中的 `control/control4.in` 与 `control/control4.ans`。 此样例满足测试点 $15\sim17$ 的限制。 **【样例 5】** 见选手文件中的 `control/control5.in` 与 `control/control5.ans`。 此样例满足测试点 $18\sim21$ 的限制。 *** **【数据范围】** 对于 $100\%$ 的数据， $2\le n\le 3~000$，$1\le k\le \min(n,1~000)$，$1\le q\le 5\times10^5$，$0\le a_i\le 1$。 |测试点编号|$n\le$|$k\le$|$q\le$|特殊性质| |:--:|:--:|:--:|:--:|:--:| |$1\sim3$|$80$|$50$|$2~000$|无| |$4\sim6$|$400$|$300$|$1$|$k$ 是偶数| |$7\sim10$|$400$|$2$|$10~000$|无| |$11\sim14$|$400$|$300$|$10~000$|无| |$15\sim17$|$3~000$|$10$|$5\times10^5$|无| |$18\sim21$|$3~000$|$1~000$|$5\times10^5$|$k$ 是偶数| |$22\sim25$|$3~000$|$1~000$|$5\times10^5$|无|