CF1404A.Balanced Bitstring

A bitstring is a string consisting only of the characters 0 and 1. A bitstring is called $k$-balanced if every substring of size $k$ of this bitstring has an equal amount of 0 and 1 characters ($\frac{k}{2}$ of each).

You are given an integer $k$ and a string $s$ which is composed only of characters 0, 1, and ?. You need to determine whether you can make a $k$-balanced bitstring by replacing every ? characters in $s$ with either 0 or 1.

A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

位串（bitstring）是指仅由字符 0 和 1 组成的字符串。若一个位串的每个长度为 $k$ 的子串都恰好包含相等数量的 0 和 1（即各 $\frac{k}{2}$ 个），则称该位串为 $k$-平衡的（$k$-balanced）。

给定一个整数 $k$ 和一个仅由字符 0、1 和 ? 组成的字符串 $s$。你需要判断：是否可以通过将 $s$ 中每个 ? 替换为 0 或 1，从而得到一个 $k$-平衡的位串。

若字符串 $a$ 可通过从字符串 $b$ 的开头删除若干（可能为零或全部）字符，并从结尾删除若干（可能为零或全部）字符而得到，则称 $a$ 是 $b$ 的一个子串（substring）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($2 \le k \le n \le 3 \cdot 10^5$, $k$ is even) — the length of the string and the parameter for a balanced bitstring.

The next line contains the string $s$ ($|s| = n$). It is given that $s$ consists of only 0, 1, and ?.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le k \le n \le 3 \cdot 10^5$，且 $k$ 为偶数）—— 分别表示字符串的长度以及平衡位串（balanced bitstring）的参数。

下一行包含字符串 $s$（$|s| = n$）。已知 $s$ 仅由字符 0、1 和 ? 组成。

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

For each test case, print YES if we can replace every ? in $s$ with 0 or 1 such that the resulting bitstring is $k$-balanced, or NO if it is not possible.

对于每个测试用例，如果我们可以将 $s$ 中的每个 ? 替换为 0 或 1，使得得到的比特串是 $k$-平衡的，则输出 YES；否则（即无法做到），输出 NO。

For the first test case, the string is already a $4$-balanced bitstring.

For the second test case, the string can be transformed into 101.

For the fourth test case, the string can be transformed into 0110.

For the fifth test case, the string can be transformed into 1100110.

对于第一个测试用例，该字符串已经是 $4$-平衡比特串。

对于第二个测试用例，该字符串可以变换为 101。

对于第四个测试用例，该字符串可以变换为 0110。

对于第五个测试用例，该字符串可以变换为 1100110。