Yuki is a cute little witch!

In front of Yuki is a zebra crossing of length $n$, which can be described by a binary string $s$ of length $n$ (1-indexed):

• If $s_i = \texttt 0$, the $i$-th position on the zebra crossing is black.
• If $s_i = \texttt 1$, the $i$-th position on the zebra crossing is white.

Yuki has a jumping ability $k$, meaning that when she is at position $x$, she can move to any position $y$ such that $\max(1, x-k) \le y \le \min(n, x+k)$ in a single jump.

Yuki will perform $q$ rounds of jumping on the zebra crossing:

• In the $i$-th round, Yuki starts at position $a_i$ and wants to reach position $b_i$ using a sequence of jumps. It is guaranteed that both $a_i$ and $b_i$ are white and $a_i \neq b_i$, i.e., $s_{a_i} = s_{b_i} = \texttt 1$ and $a_i \neq b_i$.
• If $t=0$, Yuki only wants to minimize the number of times she lands on a black position. If $t=1$, Yuki wants to minimize the number of jumps after minimizing the number of times she lands on a black position.

You need to help Yuki find the answer for each round of jumping.

(Playing around on a zebra crossing is bad behavior; children should not imitate this!)

Input

The first line contains five integers $c, n, q, k, t$, where $c$ is the test case number. $c=0$ indicates that the test case is a sample.

The second line contains a binary string $s$ of length $n$.

The next $q$ lines each contain two integers $a_i, b_i$.

Output

Output $q$ lines:

• If $t=0$, the $i$-th line contains a single integer representing the minimum number of times Yuki lands on a black position in the $i$-th round.
• If $t=1$, the $i$-th line contains two integers:
  • The minimum number of times Yuki lands on a black position in the $i$-th round.
  • The minimum number of jumps in the $i$-th round, given that the number of black positions landed on is minimized.

Examples

Input 1

0 8 3 2 1
11001111
1 7
7 5
2 5

Output 1

1 3
0 1
1 2

Note 1

For the first round:

• The only valid jumping sequence is $1 \to 3 \to 5 \to 7$.
• $1 \to 2 \to 5 \to 7$ is not valid because Yuki's jumping ability is $2$, so she cannot jump from position $2$ to $5$.
• $1 \to 2 \to 4 \to 6 \to 7$ is not valid because it does not minimize the number of jumps.

For the second round, the only valid jumping sequence is $7 \to 5$.

For the third round, the valid jumping sequences are $2 \to 3 \to 5$ and $2 \to 4 \to 5$.

Examples 2-8

See the provided files $\textit{jump/jump2.in}$ through $\textit{jump/jump8.in}$ and their corresponding $\textit{.ans}$ files. These samples satisfy the constraints for test cases $3, 7, 13, 15, 17, 19,$ and $25$ respectively.

Constraints

For all test cases, it is guaranteed that:

• $2 \le n \le 5 \times 10^5$, $1 \le q \le 5 \times 10^5$.
• $1 \le k < n$, $t \in \{0, 1\}$, $s_i \in \{\texttt 0, \texttt 1\}$.
• $1 \le a_i, b_i \le n$, $s_{a_i} = s_{b_i} = \texttt 1$, $a_i \neq b_i$.

It is guaranteed that $t=1$ for all odd-numbered test cases, and $t=0$ for all even-numbered test cases.

• Special Property A: Guaranteed $k=1$.
• Special Property B: Guaranteed that for any positive integer $i < n$, at most one of $s_i$ and $s_{i+1}$ is $\texttt 0$.
• Special Property C: Guaranteed that there is no positive integer $i \le n-k+1$ such that $s_i$ through $s_{i+k-1}$ are all $\texttt 0$.