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.


-----Input-----

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$.


-----Output-----

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.


-----Example-----
Input
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

Output
YES
YES
NO
YES
YES
NO
NO
YES
NO



-----Note-----

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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\nimport heapq, functools, collections\nimport math, random\nfrom collections import Counter, defaultdict\n\n# available on Google, not available on Codeforces\n# import numpy as np\n# import scipy\n\n\ndef solve(srr, k):  # fix inputs here\n    console("----- solving ------")\n    console(srr, k)\n\n    ones = 0\n    zeroes = 0\n\n    for i in range(k):\n        sett = set(srr[i::k])\n        if "1" in sett and "0" in sett:\n            return "NO"\n        if "1" in sett:\n            ones += 1\n        if "0" in sett:\n            zeroes += 1\n\n    if ones > k // 2 or zeroes > k // 2:\n        return "NO"\n\n    return "YES"\n\n\ndef console(*args):  # the judge will not read these print statement\n    print(\'\\033[36m\', *args, \'\\033[0m\', file=sys.stderr)\n    return\n\n# fast read all\n# sys.stdin.readlines()\n\nfor case_num in range(int(input())):\n    # read line as a string\n    # strr = input()\n\n    # read line as an integer\n    # k = int(input())\n    \n    # read one line and parse each word as a string\n    # lst = input().split()\n\n    # read one line and parse each word as an integer\n    _, k = list(map(int,input().split()))\n    srr = input()\n\n    # read matrix and parse as integers (after reading read nrows)\n    # lst = list(map(int,input().split()))\n    # nrows = lst[0]  # index containing information, please change\n    # grid = []\n    # for _ in range(nrows):\n    #     grid.append(list(map(int,input().split())))\n\n    res = solve(srr, k)  # please change\n    \n    # Google - case number required\n    # print("Case #{}: {}".format(case_num+1, res))\n\n    # Codeforces - no case number required\n    print(res)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13881