题目描述

0, 1, ? のみからなる長さ $N$ の文字列 $S=S_1S_2\dots\ S_N$ が与えられます。

これから $S$ に含まれるすべての ? を 0, 1 のいずれかに置き換えることで、以下の条件がすべて満たされるようにしたいです。

• $S$ は 1 をちょうど $K$ 個含む。
• $K$ 個の 1 は連続している。すなわち、ある $i\ (1\ \leq\ i\ \le\ N-K+1)$ があって、$S_i=S_{i+1}=\dots=S_{i+K-1}=$ 1 が成り立つ。

条件を満たすような ? の置き換え方がちょうど $1$ 通りであるか判定してください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

输入格式

入力は以下の形式で標準入力から与えられます。

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

各ケースは以下の形式で与えられます。

$N$ $K$ $S$

输出格式

$T$ 行出力してください。$i$ 行目には $i$ 番目のテストケースについて、条件を満たすような ? の置き換え方がちょうど $1$ 通りである場合は Yes を、そうでない場合は No を出力してください。

题目大意

给你一个长度为 $N$ 的字符串 $S$，仅含 0，1，?，问你能不能通过把? 变成 0 或 1，有且仅有一种方案使得这个字符串有且仅有一段连续的 1，且长度为 $K$。

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$ 以下

Sample Explanation 1

$1$ 個目のテストケースについて、例えば $S$ を 101 に変えることができますが、この場合は 1 が連続していないため、条件を満たしません。 $S$ が条件を満たすようにするには $S$ を 110 に変えるしかありません。 $2$ 個目のテストケースについて、 $S$ が条件を満たすようにするには $S$ を 1100, または 0110 に変えればよく、条件を満たすような ? の置き換え方は $2$ 通りあります。 $3$ 個目のテストケースについて、$S$ が条件を満たすよう ? を置き換える方法は存在しません。