#214687. 跳跃

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

Yuki 的面前有一条长度为 的斑马线，其可以用一个长度为 的 串 描述（下标从 开始）：

• 若 ，则表示这条斑马线上的第 个位置为黑色；
• 若 ，则表示这条斑马线上的第 个位置为白色。

同时，Yuki 有一个跳跃能力 ，表示当她位于位置 时，她可以通过一次跳跃，移动到任意一个满足 的位置 。

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

• 第 轮跳跃中，Yuki 初始时位于位置 ，她希望通过若干次跳跃恰好移动到位置 ；其中，保证位置 和位置 均为白色且 不等于 ，即 且 。
• 若 ，则 Yuki 只希望最小化她跳跃后踩到黑色位置的次数；若 ，则 Yuki 希望在最小化她跳跃后踩到黑色位置的次数的基础上，最小化跳跃次数。

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

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

第一行包含五个整数 ，其中 表示测试点编号。 表示该测试点为样例。

第二行包含一个长度为 的 串 。

接下来 行，第 行包含两个整数 。

输出 行：

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

样例输入 1

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

样例输出 1

1 3
0 1
1 2

样例 1 解释

对于第 轮跳跃：

• 唯一一种满足条件的跳跃方式为 ；
• 不满足条件，因为 Yuki 的跳跃能力为 ，无法从位置 跳跃至位置 ；
• 不满足条件，因为没有最小化跳跃次数。

对于第 轮跳跃，唯一一种满足要求的跳跃方式为 。

对于第 轮跳跃，满足要求的跳跃方式有 和 。

样例 2

见下发文件中的 与 。

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

样例 3

见下发文件中的 与 。

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

样例 4

见下发文件中的 与 。

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

样例 5

见下发文件中的 与 。

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

样例 6

见下发文件中的 与 。

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

样例 7

见下发文件中的 与 。

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

样例 8

见下发文件中的 与 。

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

数据范围

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

• ，；
• ，，；
• ，，。

保证对于所有编号为奇数的测试点都满足 ，对于所有编号为偶数的测试点都满足 。

::cute-table{tuack}

• 特殊性质 A：保证 。
• 特殊性质 B：保证对于任意小于 的正整数 ，都满足 和 中至多有一个 。
• 特殊性质 C：保证不存在不大于 的正整数 ，满足 至 均为 。