给定一个长度为 $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$ 的最小操作次数。询问之间相互独立，也就是说，每次询问后重置为初始序列。
## Input
从标准输入读入数据。
第一行包含三个正整数 $n,k,q$。
第二行包含 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$。
接下来 $q$ 行，每行包含两个正整数 $L,R$，表示一次询问。
## Output
输出到标准输出。
输出共 $q$ 行，每行包含一个整数，表示答案。
[samples]
## Note
**【样例 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$|无|