题目描述
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 输入
0 8 3 2 1 11001111 1 7 7 5 2 5
样例 1 输出
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
见下发文件中的 $\textit{jump/jump2.in}$ 与 $\textit{jump/jump2.ans}$。
该组样例满足测试点 $3$ 的限制。
样例 3
见下发文件中的 $\textit{jump/jump3.in}$ 与 $\textit{jump/jump3.ans}$。
该组样例满足测试点 $7$ 的限制。
样例 4
见下发文件中的 $\textit{jump/jump4.in}$ 与 $\textit{jump/jump4.ans}$。
该组样例满足测试点 $13$ 的限制。
样例 5
见下发文件中的 $\textit{jump/jump5.in}$ 与 $\textit{jump/jump5.ans}$。
该组样例满足测试点 $15$ 的限制。
样例 6
见下发文件中的 $\textit{jump/jump6.in}$ 与 $\textit{jump/jump6.ans}$。
该组样例满足测试点 $17$ 的限制。
样例 7
见下发文件中的 $\textit{jump/jump7.in}$ 与 $\textit{jump/jump7.ans}$。
该组样例满足测试点 $19$ 的限制。
样例 8
见下发文件中的 $\textit{jump/jump8.in}$ 与 $\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}$。
| 测试点编号 | $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$。