Alice and Bob play a game. Initially they have a string $s_1, s_2, \dots, s_n$, consisting of only characters . and X. They take alternating turns, and Alice is moving first. During each turn, the player has to select a contiguous substring consisting only of characters . and replaces each of them with X. Alice must select a substing of length $a$, and Bob must select a substring of length $b$. It is guaranteed that $a > b$.

For example, if $s =$ ...X.. and $a = 3$, $b = 2$, then after Alice's move string can turn only into XXXX... And if it's Bob's turn and the string $s =$ ...X.., then after Bob's move the string can turn into XX.X.., .XXX.. or ...XXX.

Whoever is unable to make a move, loses. You have to determine who wins if they both play optimally.

You have to answer $q$ independent queries.


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of queries.

The first line of each query contains two integers $a$ and $b$ ($1 \le b < a \le 3 \cdot 10^5$).

The second line of each query contains the string $s$ ($1 \le |s| \le 3 \cdot 10^5$), consisting of only characters . and X.

It is guaranteed that sum of all $|s|$ over all queries not exceed $3 \cdot 10^5$.


-----Output-----

For each test case print YES if Alice can win and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).


-----Example-----
Input
3
3 2
XX......XX...X
4 2
X...X.X..X
5 3
.......X..X

Output
YES
NO
YES



-----Note-----

In the first query Alice can select substring $s_3 \dots s_5$. After that $s$ turns into XXXXX...XX...X. After that, no matter what move Bob makes, Alice can make the move (this will be her second move), but Bob can't make his second move.

In the second query Alice can not win because she cannot even make one move.

In the third query Alice can choose substring $s_2 \dots s_6$. After that $s$ turns into .XXXXX.X..X, and Bob can't make a move after that.

Difficulty: interview

Starter code:

Solutions:
import os, sys

# zeilen = [l.strip() for l in sys.stdin.readlines()]

q = int(sys.stdin.readline().strip())



for _ in range(q):
  a, b = list(map(int, sys.stdin.readline().strip().split()))
  word = sys.stdin.readline().strip()
  gaps = sorted([len(gap) for gap in word.split('X') if len(gap)>= b])
  if len(gaps) == 0:
    print('NO')
  elif gaps[0] < a:
    print('NO')
  elif len(gaps) > 1 and gaps[-2] >= 2*b:
    print('NO')
  elif gaps[-1] < 2*b: # no problematic, need only count
    print('YES' if (len(gaps) % 2) else 'NO')
  else: # exactly one problematic gap
    p = gaps[-1]
    if (len(gaps) % 2): # A tries to make this gap into zero or two
      if p <= (a + 2*b - 2): # short enough for 0
        print('YES')
      elif p < 3*a: # we have to try two
        print('NO') # not long enough
      elif p > (a + 4*b - 2): # too long
        print('NO')
      else:
        print('YES')
    else: # A tries to make this gap into one
      if p < 2*a: # too short
        print('NO')
      elif p > (a + 3*b - 2):# too long
        print('NO')
      else:
        print('YES')



# import sys
# input = sys.stdin.readline

Q = int(input())
for _ in range(Q):
    a, b = list(map(int, input().split()))
    S = input() + "X"
    s = 0
    x = x1 = x2 = x3 = xx = 0
    for i in range(len(S)):
        if S[i] == "X":
            if s < b:
                pass
            elif a <= s < 2*b:
                x += 1
            elif a < 2*b and (3*a <= s < a+3*b-1 or 2*a <= s < a+2*b-1):
                xx += 1
            elif a < 2*b and 3*a <= s < a+4*b-1:
                x3 += 1
            elif a < 2*b and 2*a <= s < a+3*b-1:
                x2 += 1
            elif a <= s < a+2*b-1:
                x1 += 1
            else:
                # print("a, b, s =", a, b, s)
                print("NO")
                break
            s = 0
        else:
            s += 1
    else:
        # print("x, x1, x2, x3 =", x, x1, x2, x3)
        if xx+x1+x2+x3 >= 2:
            print("NO")
        elif xx:
            print("YES")
        elif (x + x1 + x2*2 + x3*3) % 2 == 0:
            print("NO")
        else:
            print("YES")


import sys
input = lambda: sys.stdin.readline().rstrip()

Q = int(input())
for _ in range(Q):
    a, b = list(map(int, input().split()))
    S = input() + "X"
    s = 0
    x = x1 = x2 = x3 = xx = 0
    for i in range(len(S)):
        if S[i] == "X":
            if s < b:
                pass
            elif a <= s < 2*b:
                x += 1
            elif a < 2*b and (3*a <= s < a+3*b-1 or 2*a <= s < a+2*b-1):
                xx += 1
            elif a < 2*b and 3*a <= s < a+4*b-1:
                x3 += 1
            elif a < 2*b and 2*a <= s < a+3*b-1:
                x2 += 1
            elif a <= s < a+2*b-1:
                x1 += 1
            else:
                # print("a, b, s =", a, b, s)
                print("NO")
                break
            s = 0
        else:
            s += 1
    else:
        # print("x, x1, x2, x3 =", x, x1, x2, x3)
        if xx+x1+x2+x3 >= 2:
            print("NO")
        elif xx:
            print("YES")
        elif (x + x1 + x2*2 + x3*3) % 2 == 0:
            print("NO")
        else:
            print("YES")


import sys
input = sys.stdin.readline

q=int(input())

for testcases in range(q):
    a,b=list(map(int,input().split()))
    S=input().strip()
    S+="X"

    T=[]

    NOW=0
    for s in S:
        if s==".":
            NOW+=1
        else:
            if NOW!=0:
                T.append(NOW)
            NOW=0

    count=0
    noflag=0
    other=[]
    
    for t in T:
        if b<=t<a:
            noflag=1
            break
        if a<=t<2*b:
            count+=1
        elif t>=2*b:
            other.append(t)

    if len(other)>=2:
        noflag=1

    if noflag==1:
        print("NO")
        continue
    if len(other)==0:
        if count%2==1:
            print("YES")
        else:
            print("NO")
        continue

    OTHER=other[0]

    for left in range(OTHER-a+1):
        right=OTHER-a-left

        if left>=2*b or right>=2*b or b<=left<a or b<=right<a:
            continue

        count2=count

        if left>=a:
            count2+=1
        if right>=a:
            count2+=1

        if count2%2==0:
            print("YES")
            break

    else:
        print("NO")
        
        


def solve(a, b, s):
	l = [len(x) for x in s.split('X')]
	tot = 0
	mx = 0
	
	for j in l:
		if j < b:
			continue
		if j < a:
			return 'NO'
		if j >= 2 * b:
			if mx > 0:
				return 'NO'
			mx = j
		tot += 1
	
	if mx > 0:
		if a < 2 * b:
			one = mx >= a and mx <= a + 2 * b - 2
			two = mx >= 2 * a and mx <= a + 3 * b - 2
			three = mx >= 3 * a and mx <= a + 4 * b - 2
			
			if not (one or two or three):
				return 'NO'
			if (one and two) or (two and three):
				return 'YES'
			if two:
				tot += 1
				
		if a >= 2 * b:
			if not (mx >= a and mx <= a + 2 * b - 2):
				return 'NO'
		
	if tot % 2 == 1:	
		return 'YES'
	else:
		return 'NO'
			
q = int(input())


for i in range(q):
	a, b = list(map(int, input().split()))
	s = input()
	print(solve(a, b, s))


def removeX(s,p):
	if (p==len(s)):
		return s
	while s[p]!='X':
		p+=1
		if (p==len(s)):
			return s
	j=0
	while s[p+j]=='X':
		j+=1
		if (p+j==len(s)):
			break
	return removeX(s[0:p+1]+s[p+j:],p+1)

def doable(lenght,a,b,parity):
	for x in range((lenght-a)//2+1): 
		y=lenght-a-x
		#print(x,y)
		if ((not((x>=b) & (x<a)))&(not(x>=2*b))&(not((y>=b) & (y<a)))&(not(y>=2*b))):
			e=0
			#print('oui')
			if((x>=a)&(x<2*b)):
				e+=1
			if((y>=a)&(y<2*b)):
				e+=1
			if((parity+e)%2==0):
				return 1
	return 0

for i in range(int(input())):
	a,b=[int(x) for x in input().split()]
	v=[0,0,0]
	s=removeX(input(),0)
	for y in s.split('X'):
		k=len(y)
		if ((k>=b) & (k<a)):
			v[0]+=1
		elif ((k>=a) & (k<2*b)):
			v[1]+=1
		elif (k>=2*b):
			v[2]+=1
			lenght=k
	#print(v)
	if ((v[0]>0) | (v[2]>1)):
		print('NO')
	elif (v[2]==1):
		if (lenght-a>=4*b):
			print('NO')
		else:
			if (doable(lenght,a,b,v[1]%2)==1):
				print('YES')
			else:
				print('NO')
	else:
		if (v[1]%2==0):
			print('NO')
		else:
			print('YES')



test_case = int(input())


def solve():
    a, b = list(map(int, input().split()))
    s = input().split('X')
    lens = [len(dot) for dot in s]
    cnt = 0
    tmp = 0
    for le in lens:
        if le < b:
            continue
        if le < a:
            return "NO"
        if le >= 2 * b:
            if tmp > 0:
                return "NO"
            tmp = le
        else:
            cnt += 1

    if tmp is not 0:
        win = False
        for i in range(tmp+1):
            part2 = tmp - i - a
            if i > part2 or i >= 2 * b:
                break
            if 2*b <= part2 or b <= i < a or b <= part2 < a:
                continue
            ncnt = cnt
            if i >= a:
                ncnt += 1
            if part2 >= a:
                ncnt += 1
            if ncnt % 2 is 0:
                win = True
    else:
        win = cnt % 2 == 1
    return "YES" if win else "NO"


for _ in range(test_case):
    print(solve())


def sol():
    a, b = map(int, input().split())
    s = input().replace("X", " ")
    small_segs = 0
    critical_region = -1

    for p in map(len, s.split()):
        if p < b:
            continue
        if p < a and p >= b:
            return False
        if ((p - a) % 2 == 0 and (p >= a + 4 * b)) or ((p - a) % 2 == 1 and p >= a + 4 * b - 1):
            return False
        if p >= 2*b:
            if critical_region != -1:
                return False
            critical_region = p
        elif p >= a:
            small_segs += 1
    
    if critical_region == -1:
        return small_segs % 2 == 1

    can = [0] * 3
    for l in range(critical_region+1-a):
        r = critical_region - l - a
        if (l >= b and l < a) or l >= 2 * b:
            continue
        if (r >= b and r < a) or r >= 2 * b:
            continue
        canl = int(l >= a)
        canr = int(r >= a)
        can[canl + canr] = 1

    for choice, val in enumerate(can):
        if val and (small_segs + choice) % 2 == 0:
            return True

    return False



n = int(input())

for _ in range(n):
    print("YES" if sol() else "NO")

def sol():
    a, b = map(int, input().split())
    s = input().replace("X", " ")
    small_segs = 0
    critical_region = -1
     
    for p in map(len, s.split()):
        if p < b:
            continue
        if p < a and p >= b:
            return False
        if ((p - a) % 2 == 0 and (p >= a + 4 * b)) or ((p - a) % 2 == 1 and p >= a + 4 * b - 1):
            return False
        if p >= 2*b:
            if critical_region != -1:
                return False
            critical_region = p
        elif p >= a:
            small_segs += 1
    
    if critical_region == -1:
        return small_segs % 2 == 1
     
    can = [0] * 3
    for l in range(critical_region+1-a):
        r = critical_region - l - a
        if (l >= b and l < a) or l >= 2 * b:
            continue
        if (r >= b and r < a) or r >= 2 * b:
            continue
        canl = int(l >= a)
        canr = int(r >= a)
        can[canl + canr] = 1
     
    for choice, val in enumerate(can):
        if val and (small_segs + choice) % 2 == 0:
            return True
     
    return False

n = int(input())
     
for _ in range(n):
    print("YES" if sol() else "NO")

test_case = int(input())
 
 
def solve():
    a, b = list(map(int, input().split()))
    s = input().split('X')
    lens = [len(dot) for dot in s]
    cnt = 0
    tmp = 0
    for le in lens:
        if le < b:
            continue
        if le < a:
            return "NO"
        if le >= 2 * b:
            if tmp > 0:
                return "NO"
            tmp = le
        else:
            cnt += 1
 
    if tmp is not 0:
        win = False
        for i in range(tmp+1):
            part2 = tmp - i - a
            if i > part2 or i >= 2 * b:
                break
            if 2*b <= part2 or b <= i < a or b <= part2 < a:
                continue
            ncnt = cnt
            if i >= a:
                ncnt += 1
            if part2 >= a:
                ncnt += 1
            if ncnt % 2 is 0:
                win = True
    else:
        win = cnt % 2 == 1
    return "YES" if win else "NO"
 
 
for _ in range(test_case):
    print(solve())


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
  a,b = map(int,input().split())
  s = input()
  n = len(s)
  ls = []
  if s[0] == ".":
    cnt = 1
  else:
    cnt = 0
  for i in range(1,n+1):
    if i < n and s[i] == ".":
      cnt += 1
    else:
      if cnt >= b:
        ls.append(cnt)
      cnt = 0
  if not ls:
    print("NO")
    continue
  ls.sort()
  if a >= 2*b:
    if len(ls) >= 2 or ls[0] > a+(b-1)*2 or ls[0] < a:
      print("NO")
    else:
      print("YES")
  else:
    if ls[0] < a:# or ls[-1] > a+(2*b-1)*2:
      print("NO")
    elif len(ls) >= 2 and ls[-2] >= 2*b:
      print("NO")
    else:
      l = len(ls)-1
      t = ls[-1]
      for i in range(t):
        if i+a <= t:
          p,q = i,t-(i+a)
          if not (b<=p<a or b<=q<a or p>=2*b or q>=2*b):
            x = l+(a<=p<2*b)+(a<=q<2*b)
            if x%2 == 0:
              print("YES")
              break
      else:
        print("NO")

import sys
input = sys.stdin.readline

def solve_case():
    a, b = [int(x) for x in input().split()]
    s = [len(x) for x in input().rstrip().split('X')]
    
    c, m = 0, 0
    
    for x in s:
        if x < b:
            continue
        elif x < a:
            print('NO')
            return
        elif x < 2*b:
            c += 1
        elif m:
            print('NO')
            return
        else:
            m = x
    
    if not m:
        if c & 1:
            print('YES')
        else:
            print('NO')
    else:
        for x in range((m - a) // 2 + 1):
            if (b <= x and x < a) or (x >= 2*b) or (b <= m - x - a and m - x - a < a) or (m - x - a >= 2*b):
                continue
            cur = c + (x >= a) + (m - x - a >= a)
            if not cur & 1:
                print('YES')
                return
        print('NO')
            
for _  in range(int(input())):
    solve_case()