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.

Difficulty: competition

Starter code:

Solutions:
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    s = input()
    l = ['']*k
    works = True
    for i in range(n):
        c = s[i]
        if c != '?':
            if l[i%k] == c or l[i%k] == '':
                l[i%k] = c
            else:
                works = False
                break
    if works:
        smol = 0
        big = k
        for c in l:
            if c == '0':
                big -= 1
            elif c == '1':
                smol += 1
        goal = k//2
        if smol <= goal <= big:
            print('YES')
        else:
            print('NO')
    else:
        print('NO')


import sys
readline = sys.stdin.readline

T = int(readline())
Ans = ['NO']*T
for qu in range(T):
    N, K = map(int, readline().split())
    S = [-1 if s == '?' else int(s) for s in readline().strip()]    
    L = [-1]*K
    for i in range(N):
        j = i%K
        si = S[i]
        if L[j] == -1:
            L[j] = si
        elif S[i] == -1:
            continue
        else:
            if L[j] != si:
                break
    else:
        one = 0
        zero = 0
        minus = 0
        for l in L:
            if l == 1:
                one += 1
            elif l == 0:
                zero += 1
            else:
                minus += 1
        
        if one < zero:
            one, zero = zero, one
        
        if zero + minus >= one:
            Ans[qu] = 'YES'
        

print('\n'.join(Ans))

import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(srr, k):  # fix inputs here
    console("----- solving ------")
    console(srr, k)

    ones = 0
    zeroes = 0

    for i in range(k):
        sett = set(srr[i::k])
        if "1" in sett and "0" in sett:
            return "NO"
        if "1" in sett:
            ones += 1
        if "0" in sett:
            zeroes += 1

    if ones > k // 2 or zeroes > k // 2:
        return "NO"

    return "YES"


def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
# sys.stdin.readlines()

for case_num in range(int(input())):
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    _, k = list(map(int,input().split()))
    srr = input()

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    # grid = []
    # for _ in range(nrows):
    #     grid.append(list(map(int,input().split())))

    res = solve(srr, k)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)


import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    n,k=list(map(int,input().split()))
    S=input().strip()

    A=[-1]*k

    for i in range(n):
        if S[i]=="0":
            if A[i%k]==1:
                print("NO")
                break
            else:
                A[i%k]=0

        if S[i]=="1":
            if A[i%k]==0:
                print("NO")
                break
            else:
                A[i%k]=1
    else:
        Z=0
        O=0
        for i in range(k):
            if A[i]==0:
                Z+=1
            if A[i]==1:
                O+=1
        if Z>k//2 or O>k//2:
            print("NO")
        else:
            print("YES")
            


mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    for _ in range(int(input())):
        N, K = list(map(int, input().split()))
        S = input().rstrip('\n')

        N0 = 0
        N1 = 0
        ok = 1
        for k in range(K):
            flg = -1
            for j in range(N):
                i = j*K+k
                if i >= N:
                    break
                if S[i] == "0":
                    if flg == 1:
                        ok = 0
                    else:
                        flg = 0
                elif S[i] == "1":
                    if flg == 0:
                        ok = 0
                    else:
                        flg = 1
            if flg == 0:
                N0 += 1
            elif flg == 1:
                N1 += 1
        if N0*2 <= K and N1*2 <= K and ok == 1:
            print("YES")
        else:
            print("NO")


def __starting_point():
    main()

__starting_point()

import sys
input = sys.stdin.readline
for f in range(int(input())):
    n,k=list(map(int,input().split()))
    s=input()
    poss=True
    sol=[2]*n
    ones=0
    zeros=0
    for i in range(n):
        if i<k:
            if s[i]=="1":
                sol[i]=1
                ones+=1
            if s[i]=="0":
                sol[i]=0
                zeros+=1
        else:
            if s[i]=="1":
                sol[i]=1
                if sol[i-k]==0:
                    poss=False
                if sol[i-k]==2:
                    ones+=1
            if s[i]=="0":
                sol[i]=0
                if sol[i-k]==1:
                    poss=False
                if sol[i-k]==2:
                    zeros+=1
            if s[i]=="?":
                if sol[i-k]==1:
                    sol[i]=1
                if sol[i-k]==0:
                    sol[i]=0
    if not poss or ones>k//2 or zeros>k//2:
        print("NO")
    else:
        print("YES")