题目描述

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

你需要将 $S$ 中所有的 ? 替换为 0 或 1，使得以下所有条件都被满足：

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

请判断是否存在恰好 $1$ 种将所有 ? 替换为 0 或 1 的方式，使得上述条件被满足。

有 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入按以下格式从标准输入读入。

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

每组数据格式如下：

$N$ $K$ $S$

输出格式

请输出 $T$ 行。对于第 $i$ 组测试数据，如果存在恰好 $1$ 种将 ? 替换为 0 或 1 的方式使得条件被满足，则输出 Yes，否则输出 No。

样例 1

输入

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

输出

Yes
No
No
Yes

说明/提示

限制

• $1 \leq T \leq 10^5$
• $1 \leq K < N \leq 3 \times 10^5$
• $S$ 是只包含 0、1、? 的长度为 $N$ 的字符串
• 所有测试数据中 $N$ 的总和不超过 $3 \times 10^5$

样例解释 1

对于第 $1$ 组测试数据，例如可以将 $S$ 变为 101，但此时 1 不连续，不满足条件。要使 $S$ 满足条件，只能将 $S$ 变为 110，只有这一种方式。

对于第 $2$ 组测试数据，可以将 $S$ 变为 1100 或 0110，有 $2$ 种方式满足条件。

对于第 $3$ 组测试数据，不存在任何方式可以通过替换 ? 使 $S$ 满足条件。

由 ChatGPT 4.1 翻译