题目描述

给定一个长度为 $N$ 的字符串 $S=S_1S_2\\dots S_N$，其中包含 0、1 和 ?。

我们希望将每个 ? 替换为 0 或 1，以满足以下所有条件：

• $S$ 中恰好包含 $K$ 个 1。
• 这 $K$ 个 1 是连续的。也就是说，存在一个 $i\\ (1 \\leq i \\le N-K+1)$，使得 $S_i=S_{i+1}=\\dots=S_{i+K-1}=$ 1。

确定是否存在唯一的替换方式以满足条件。

你需要解决 $T$ 个测试用例。

约束条件

• $1 \\leq T \\leq 10^5$
• $1 \\leq K < N \\leq 3 \\times 10^5$
• $S$ 是一个长度为 $N$ 的字符串，由 0、1 和 ? 组成。
• 所有测试用例中 $N$ 的总和不超过 $3 \\times 10^5$。

输入

输入数据从标准输入读入，格式如下：

$T$ $\\mathrm{case}_1$ $\\vdots$ $\\mathrm{case}_T$

每个测试用例的格式如下：

$N$ $K$ $S$

输出

输出 $T$ 行。第 $i$ 行应该包含 Yes，如果对于第 $i$ 个测试用例，存在唯一的替换方式以满足条件；否则，输出 No。

示例输入 1

4
3 2
1??
4 2
?1?0
6 3
011?1?
10 5
00?1???10?

示例输出 1

Yes
No
No
Yes

对于第一个测试用例，例如将 $S$ 变为 101 并不满足条件，因为 1 不是连续的。惟一满足条件的方法是将 $S$ 变为 110。

对于第二个测试用例，我们可以将 $S$ 变为 1100 或 0110 来满足条件，所以有两种满足条件的方法。

对于第三个测试用例，没有办法替换字符以满足条件。