Minimizing Operations to Reduce Ones

You are given a binary (0/1) sequence \(a_1,a_2,\dots,a_n\) of length \(n\) and an integer \(k\). There are \(q\) independent queries. In each query, you are given two indices \(L\) and \(R\) (with \(1\le L\le R\le n\)). In the query you are allowed to perform the following operation any number of times (possibly zero):

• Choose an index \(i\) such that \(L < i \le R\) (note that \(i\) is chosen from the interval \([L+1,R]\)).
• Then update \(a_{i-1}\) and \(a_{i+1}\) as follows: \[ a_{i-1} \leftarrow a_{i-1} \oplus a_i, \quad a_{i+1} \leftarrow \begin{cases} a_{i+1} \oplus a_i, & \text{if } i < n, \\ a_{i+1} \text{ is not changed}, & \text{if } i=n. \end{cases} \] Here \(\oplus\) denotes the bitwise XOR operation.

After applying some operations (each operation is applied on the original sequence independently per query), your goal is to make the number of ones in the subarray \(a_L,a_{L+1},\dots,a_R\) at most \(k\). Find the minimum number of operations needed. If it is impossible, output -1.

Note: The operations in different queries are independent (the sequence is reset between queries).

inputFormat

The first line contains three integers \(n\), \(q\), and \(k\) separated by spaces.

The second line contains a binary string of length \(n\) (each character is either 0 or 1) representing the sequence \(a\).

Then \(q\) lines follow. Each of these lines contains two integers \(L\) and \(R\) representing a query.

outputFormat

For each query, output a single line containing the minimum number of operations needed to make the number of ones in \(a_L, a_{L+1}, \dots, a_R\) at most \(k\). If it is impossible, output -1.

sample

5 3 1
11111
1 5
2 4
3 5

2
1
1