← 返回题目列表

Codeforces · 1404/A

A. 平衡位串

中文机器翻译题面 查看原题

位串是仅由字符 0 和 1 组成的字符串。如果该位串的每个大小为 $$$k$$$ 的子串具有相等数量的 0 和 1 个字符(每个 $$$\frac{k}{2}$$$),则该位串称为 $$$k$$$ 平衡的。

给定一个整数 $$$k$$$ 和一个仅由字符 0、1 和 ? 组成的字符串 $$$s$$$。您需要确定是否可以通过替换每个 ? 来创建 $$$k$$$ 平衡的位串。 $$$s$$$ 中的字符为 0 或 1。

字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le k \le n \le 3 \cdot 10^5$$$, $$$k$$$ 是偶数) — 字符串的长度和平衡位串的参数。

下一行包含字符串 $$$s$$$ ($$$|s| = n$$$)。假设 $$$s$$$ 仅由 0、1 和 ? 组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,如果我们可以替换每个 ? 则打印 YES在 $$$s$$$ 中为 0 或 1,这样生成的位串是 $$$k$$$ 平衡的,如果不可能,则为 NO。

示例

输入 #1

9
6 4
100110
3 2
1?1
3 2
1?0
4 4
????
7 4
1?0??1?
10 10
11??11??11
4 2
1??1
4 4
?0?0
6 2
????00

输出 #1

YES
YES
NO
YES
YES
NO
NO
YES
NO

注意

对于第一个测试用例,字符串已经是 $$$4$$$ 平衡的位串。

对于第二个测试用例,可以将字符串转换为 101。

对于第四个测试用例,可以将字符串转换为0110。

对于第五个测试用例,可以将字符串转换为 1100110。