配点 : $300$ 点

問題文

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$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• $1 \leq T \leq 10^5$
• $1 \leq K < N \leq 3 \times 10^5$
• $S$ は 0, 1, ? のみからなる長さ $N$ の文字列
• 全テストケースに対する $N$ の総和は $3 \times 10^5$ 以下

入力

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

$T$

$\mathrm{case}_1$

$\vdots$

$\mathrm{case}_T$

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

$N$ $K$

$S$

出力

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

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

Yes
No
No
Yes

$1$ 個目のテストケースについて、例えば $S$ を 101 に変えることができますが、この場合は 1 が連続していないため、条件を満たしません。 $S$ が条件を満たすようにするには $S$ を 110 に変えるしかありません。

$2$ 個目のテストケースについて、 $S$ が条件を満たすようにするには $S$ を 1100, または 0110 に変えればよく、条件を満たすような ? の置き換え方は $2$ 通りあります。

$3$ 個目のテストケースについて、$S$ が条件を満たすよう ? を置き換える方法は存在しません。