Problem Description

You are given a $\tt01$ sequence $a$ of length $n$ and $q$ queries, with query parameter $k$.

In each query, you are given $L, R$ with $1 \le L \le R \le n$. You may perform the following operation:

• Choose an index $L < i \le R$.
• Set $a_{i-1}$ to $a_{i-1} \oplus a_i$, and set $a_{i+1}$ to $a_{i+1} \oplus a_i$. If $i = n$, then $a_{i+1}$ is not changed. Here $\oplus$ denotes the bitwise XOR operation.

Find the minimum number of operations needed so that there are at most $k$ $\tt1$'s in the interval $[L, R]$. The queries are independent, meaning that after each query, the sequence is reset to the initial sequence.

Input Format

Read input from standard input.

The first line contains three positive integers $n, k, q$.

The second line contains $n$ non-negative integers $a_1, a_2, \cdots, a_n$.

The next $q$ lines each contain two positive integers $L, R$, representing one query.

Output Format

Write output to standard output.

Output $q$ lines in total, each containing one integer, the answer for the corresponding query.

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

Hint

[Sample 1 Explanation]

As shown in the figure, green represents $\tt0$ and red represents $\tt1$. The initial sequence is as follows:

For the 1st query, choose $i = 3$, and the sequence becomes:

For the 2nd query, choose $i = 2$, and the sequence becomes:

[Sample 2 Explanation]

For the 1st query, since among $a_{12}, a_{13}, a_{14}, a_{15}$ there are only $2$ $\tt1$'s, no operation is needed.

For the 6th query, you can choose $i = \{7, 8, 9, 10, 11, 12\}$ in order.

[Sample 3]

See control/control3.in and control/control3.ans in the contestant files.

This sample satisfies the constraints of test points $7 \sim 10$.

[Sample 4]

See control/control4.in and control/control4.ans in the contestant files.

This sample satisfies the constraints of test points $15 \sim 17$.

[Sample 5]

See control/control5.in and control/control5.ans in the contestant files.

This sample satisfies the constraints of test points $18 \sim 21$.

[Constraints]

For $100\%$ of the testdata: $2 \le n \le 3~000$, $1 \le k \le \min(n, 1~000)$, $1 \le q \le 5 \times 10^5$, $0 \le a_i \le 1$.

Translated by ChatGPT 5