罗斯坦的忠诚马拉赫什 (Rakhsh) 已经过上了好日子。拉赫什曾经强大而快速,但随着时间的推移,它变得越来越虚弱,甚至连移动都困难。罗斯坦担心,如果拉赫什身体的太多部位同时失去力量,拉赫什可能会完全停止运动。为了让他的同伴继续前进,罗斯坦决定一点一点地增强拉赫什的力量,这样他身体的任何部位都不会太脆弱太久。
将 Rakhsh 的身体想象成一排点,由长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 表示,其中每个 $$$0$$$ 表示一个弱点,每个 $$$1$$$ 表示一个强点。 Rostam 的目标是确保没有 $$$m$$$ 连续点的间隔是完全弱的(所有 $$$0$$$s)。
幸运的是,罗斯坦有一种叫做蒂玛的特殊能力,这是他出生时从母亲鲁达贝那里继承的。使用 Timar,他可以选择任何长度为 $$$k$$$ 的片段并立即强化所有片段(将该片段中的每个字符更改为 $$$1$$$)。挑战在于计算 Rostam 需要使用 Timar 来保持 Rakhsh 移动的最少次数,确保不存在长度为 $$$m$$$ 的连续完全弱点。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$),测试用例的数量。
每个测试用例的第一行包含三个数字 $$$n$$$、$$$m$$$、$$$k$$$ ($$$1 \le m, k \le n \le 2 \cdot 10^5$$$)。每个测试用例的第二行包含一个由 $$$n$$$ 个字符 $$$s_1s_2 \ldots s_n$$$ 组成的二进制字符串 $$$s$$$。 ($$$s_i \in \{$$$0,1$$$\}$$$ for $$$1 \le i \le n$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 Rostam 需要使用 Timar 来保持 Rakhsh 移动的最小次数,确保不存在长度为 $$$m$$$ 的连续完全弱点。
示例
输入 #1
3 5 1 1 10101 5 2 1 10101 6 3 2 000000
输出 #1
2 0 1
注意
在第一个测试用例中,我们应该对每个 0 进行操作。
在第二个测试用例中,$$$s$$$ 已经可以了。
在第三个测试用例中,我们可以对区间 $$$[3,4]$$$ 进行运算,得到 001100。