题目描述

Yuki 是一个可可爱爱的小魔女！

Yuki 的面前有一条长度为 $n$ 的斑马线，其可以用一个长度为 $n$ 的 $\texttt{01}$ 串 $s$ 描述（下标从 $1$ 开始）：

• 若 $s_i=\texttt 0$，则表示这条斑马线上的第 $i$ 个位置为黑色；
• 若 $s_i=\texttt 1$，则表示这条斑马线上的第 $i$ 个位置为白色。

同时，Yuki 有一个跳跃能力 $k$，表示当她位于位置 $x$ 时，她可以通过一次跳跃，移动到任意一个满足 $\max(1,x-k)\le y\le \min(n,x+k)$ 的位置 $y$。

接下来，Yuki 会在斑马线上进行 $q$ 轮跳跃：

• 第 $i$ 轮跳跃中，Yuki 初始时位于位置 $a_i$，她希望通过若干次跳跃恰好移动到位置 $b_i$；其中，保证位置 $\boldsymbol{a_i}$ 和位置 $\boldsymbol{b_i}$ 均为白色且 $\boldsymbol{a_i}$ 不等于 $\boldsymbol{b_i}$，即 $s_{a_i}=s_{b_i}=\texttt 1$ 且 $a_i \ne b_i$。
• 若 $t=0$，则 Yuki 只希望最小化她跳跃后踩到黑色位置的次数；若 $t=1$，则 Yuki 希望在最小化她跳跃后踩到黑色位置的次数的基础上，最小化跳跃次数。

Yuki 需要你帮助她求出每轮跳跃的答案。

（在斑马线上嬉戏打闹是不好的行为，小朋友不要学！）

输入格式

第一行包含五个整数 $c,n,q,k,t$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含一个长度为 $n$ 的 $\texttt{01}$ 串 $s$。

接下来 $q$ 行，第 $i$ 行包含两个整数 $a_i,b_i$。

输出格式

输出 $q$ 行：

• 若 $t=0$，则第 $i$ 行包含一个整数，表示第 $i$ 轮跳跃中，Yuki 跳跃后踩到黑色位置的次数的最小值；
• 若 $t=1$，则第 $i$ 行包含两个整数，分别表示：
  • 第 $i$ 轮跳跃中，Yuki 跳跃后踩到黑色位置的次数的最小值；
  • 第 $i$ 轮跳跃中，在最小化 Yuki 跳跃后踩到黑色位置的次数的基础上，Yuki 跳跃次数的最小值。

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

1 3
0 1
1 2

提示

样例 1 解释

对于第 $1$ 轮跳跃：

• 唯一一种满足条件的跳跃方式为 $1 \to 3 \to 5 \to 7$；
• $1 \to 2 \to5\to7$ 不满足条件，因为 Yuki 的跳跃能力为 $2$，无法从位置 $2$ 跳跃至位置 $5$；
• $1 \to 2 \to 4 \to 6\to 7$ 不满足条件，因为没有最小化跳跃次数。

对于第 $2$ 轮跳跃，唯一一种满足要求的跳跃方式为 $7 \to 5$。

对于第 $3$ 轮跳跃，满足要求的跳跃方式有 $2 \to 3 \to 5$ 和 $2 \to 4 \to 5$。

样例 2

见下发文件中的 $\textbf{\textit{jump/jump2.in}}$ 与 $\textbf{\textit{jump/jump2.ans}}$。

该组样例满足测试点 $3$ 的限制。

样例 3

见下发文件中的 $\textbf{\textit{jump/jump3.in}}$ 与 $\textbf{\textit{jump/jump3.ans}}$。

该组样例满足测试点 $7$ 的限制。

样例 4

见下发文件中的 $\textbf{\textit{jump/jump4.in}}$ 与 $\textbf{\textit{jump/jump4.ans}}$。

该组样例满足测试点 $13$ 的限制。

样例 5

见下发文件中的 $\textbf{\textit{jump/jump5.in}}$ 与 $\textbf{\textit{jump/jump5.ans}}$。

该组样例满足测试点 $15$ 的限制。

样例 6

见下发文件中的 $\textbf{\textit{jump/jump6.in}}$ 与 $\textbf{\textit{jump/jump6.ans}}$。

该组样例满足测试点 $17$ 的限制。

样例 7

见下发文件中的 $\textbf{\textit{jump/jump7.in}}$ 与 $\textbf{\textit{jump/jump7.ans}}$。

该组样例满足测试点 $19$ 的限制。

样例 8

见下发文件中的 $\textbf{\textit{jump/jump8.in}}$ 与 $\textbf{\textit{jump/jump8.ans}}$。

该组样例满足测试点 $25$ 的限制。

数据范围

对于所有测试数据，保证：

• $2 \le n\le 5\times10^5$，$1 \le q \le 5\times10^5$；
• $1 \le k \lt 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 \ne b_i$。

保证对于所有编号为奇数的测试点都满足 $\boldsymbol{t=1}$，对于所有编号为偶数的测试点都满足 $\boldsymbol{t=0}$。

::cute-table{tuack}

测试点编号	$n \le$	$q \le$	特殊性质
$1\sim2$	$400$		C
$3\sim4$			无
$5\sim6$	$2000$	$2000$	C
$7\sim10$			无
$11\sim12$		$5\times10^5$	C
$13\sim14$			无
$15\sim16$	$5\times10^5$		A
$17\sim18$			B
$19\sim20$			C
$21\sim25$			无

• 特殊性质 A：保证 $k=1$。
• 特殊性质 B：保证对于任意小于 $n$ 的正整数 $i$，都满足 $s_i$ 和 $s_{i+1}$ 中至多有一个 $\texttt{0}$。
• 特殊性质 C：保证不存在不大于 $n-k+1$ 的正整数 $i$，满足 $s_i$ 至 $s_{i+k-1}$ 均为 $\texttt 0$。