Бинарная строка это строка, состоящая только из символов 0 и 1. Бинарная строка называется \(k\)-сбалансированной, если каждая подстрока длины \(k\) этой бинарной строки содержит равное количество символов 0 и 1 (\(\frac{k}{2}\) каждого).
Вам дается целое число \(k\) и строка \(s\), состоящая только из символов 0, 1 и ?. Вам необходимо определить, можно ли получить \(k\)-сбалансированную бинарную строку, заменив каждый символ ? в \(s\) либо на 0, либо на 1.
Строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Выходные данные
Для каждого набора входных данных выведите YES, если мы можем заменить каждый ? в \(s\) на 0 или 1 так, чтобы получившаяся бинарная строка была \(k\)-сбалансированной, или NO если это невозможно.
Примечание
В первом наборе входных данных строка уже является \(4\)-сбалансированной бинарной строкой.
Во втором наборе входных данных строка может быть преобразована в 101.
В третьем наборе входных данных строку можно преобразовать в 0110.
В четвертом наборе входных данных строку можно преобразовать в 1100110.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|