P14563 跳跃

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 跳跃次数的最小值。

### 样例 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$ | $400$ | C | | $3\sim4$ | $400$ | $400$ | 无 | | $5\sim6$ | $2000$ | $2000$ | C | | $7\sim10$ | $2000$ | $2000$ | 无 | | $11\sim12$ | $2000$ | $5\times10^5$ | C | | $13\sim14$ | $2000$ | $5\times10^5$ | 无 | | $15\sim16$ | $5\times10^5$ | $5\times10^5$ | A | | $17\sim18$ | $5\times10^5$ | $5\times10^5$ | B | | $19\sim20$ | $5\times10^5$ | $5\times10^5$ | C | | $21\sim25$ | $5\times10^5$ | $5\times10^5$ | 无 | - 特殊性质 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$。