题目描述

给定一个长度为 $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$。