A. Сбалансированная бинарная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бинарная строка это строка, состоящая только из символов 0 и 1. Бинарная строка называется $$$k$$$-сбалансированной, если каждая подстрока длины $$$k$$$ этой бинарной строки содержит равное количество символов 0 и 1 ($$$\frac{k}{2}$$$ каждого).

Вам дается целое число $$$k$$$ и строка $$$s$$$, состоящая только из символов 0, 1 и ?. Вам необходимо определить, можно ли получить $$$k$$$-сбалансированную бинарную строку, заменив каждый символ ? в $$$s$$$ либо на 0, либо на 1.

Строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.

Входные данные

Каждый тест содержит несколько наборов входных данных. В первой строке указано количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$). Описание наборов входных данных приведено ниже.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le k \le n \le 3 \cdot 10^5$$$, $$$k$$$ чётное)  — длина строки и параметр для сбалансированной бинарной строки.

Следующая строка содержит строку $$$s$$$ ($$$|s| = n$$$). При этом $$$s$$$ состоит только из 0, 1 и ?.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите YES, если мы можем заменить каждый ? в $$$s$$$ на 0 или 1 так, чтобы получившаяся бинарная строка была $$$k$$$-сбалансированной, или NO если это невозможно.

Пример
Входные данные
9
6 4
100110
3 2
1?1
3 2
1?0
4 4
????
7 4
1?0??1?
10 10
11??11??11
4 2
1??1
4 4
?0?0
6 2
????00
Выходные данные
YES
YES
NO
YES
YES
NO
NO
YES
NO
Примечание

В первом наборе входных данных строка уже является $$$4$$$-сбалансированной бинарной строкой.

Во втором наборе входных данных строка может быть преобразована в 101.

В третьем наборе входных данных строку можно преобразовать в 0110.

В четвертом наборе входных данных строку можно преобразовать в 1100110.