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: VERY_HARD
Tags: Game theory

Starter code:

Solutions:
import sys
input = sys.stdin.readline
q = int(input())
for testcases in range(q):
	(a, b) = 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))


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())


Q = int(input())
for _ in range(Q):
	(a, b) = 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('NO')
				break
			s = 0
		else:
			s += 1
	else:
		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')


q = int(input())
for i in range(q):
	(a, b) = [int(item) for item in input().split()]
	s = input().rstrip() + '#'
	cnt = 0
	bob_world = 0
	alice_world = 0
	length = 0
	bob_winning = False
	for ch in s:
		if ch == '.':
			cnt += 1
		else:
			if cnt < b:
				pass
			elif b <= cnt < a:
				bob_winning = True
				break
			elif a <= cnt < b * 2:
				alice_world += 1
			elif cnt >= b * 2:
				length = cnt
				bob_world += 1
				if bob_world >= 2:
					bob_winning = True
					break
			cnt = 0
	if bob_winning:
		print('No')
	else:
		if length == 0:
			if alice_world % 2 == 1:
				print('Yes')
			else:
				print('No')
			continue
		possibility = set()
		for i in range(length - a + 1):
			l = i
			r = length - a - i
			if b <= l < a or b <= r < a:
				continue
			if l >= b * 2 or r >= b * 2:
				continue
			val = 0
			if a <= l < b * 2:
				val += 1
			if a <= r < b * 2:
				val += 1
			possibility.add(val + 1)
		alice_win = False
		for item in possibility:
			if (alice_world + item) % 2 == 1:
				alice_win = True
		if alice_win:
			print('Yes')
		else:
			print('No')


import sys
from itertools import groupby
readline = sys.stdin.readline
t = int(input())
for _ in range(t):
	(a, b) = map(int, readline().split())
	dots = [len(list(v)) for (k, v) in groupby(readline().rstrip()) if k == '.']
	lose = 0
	med = 0
	long = 0
	longest = 0
	for x in dots:
		if x < b:
			continue
		if b <= x < a:
			lose = 1
		elif 2 * b <= x:
			long += 1
			if longest < x:
				longest = x
		elif a <= x < 2 * b:
			med += 1
	if lose or long > 1:
		print('NO')
		continue
	if long:
		for (left, right) in zip(range(longest), range(longest - a, -1, -1)):
			if (left < b or a <= left < 2 * b) and (right < b or a <= right < 2 * b):
				if med + (1 if a <= left else 0) + (1 if a <= right else 0) & 1 == 0:
					print('YES')
					break
		else:
			print('NO')
	else:
		print('YES' if med & 1 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')


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('NO')
				break
			s = 0
		else:
			s += 1
	else:
		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')


def main():
	import sys
	input = sys.stdin.readline
	q = int(input())
	for _ in range(q):
		(a, b) = map(int, input().split())
		S = input().rstrip('\n')
		S += '!'
		win = 1
		cnt = 0
		flg = 0
		num = 0
		for s in S:
			if s == '.':
				cnt += 1
			else:
				if cnt:
					if b <= cnt < a:
						win = 0
						break
					elif cnt < b:
						pass
					elif cnt < 2 * b:
						num += 1
					else:
						num += 1
						if flg:
							flg = 2
							win = 0
							break
						else:
							flg = 1
							tmp = cnt
				cnt = 0
		if flg == 1:
			if num % 2 == 0:
				if a >= 2 * b:
					win = 0
				elif not 2 * a <= tmp <= a + 3 * b - 2:
					win = 0
			elif tmp <= a + 2 * b - 2:
				pass
			elif 3 * a <= tmp <= a + 4 * b - 2:
				pass
			else:
				win = 0
		elif flg == 0:
			if num % 2 == 0:
				win = 0
		if win:
			print('Yes')
		else:
			print('No')
main()


import os, sys
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:
		print('YES' if len(gaps) % 2 else 'NO')
	else:
		p = gaps[-1]
		if len(gaps) % 2:
			if p <= a + 2 * b - 2:
				print('YES')
			elif p < 3 * a:
				print('NO')
			elif p > a + 4 * b - 2:
				print('NO')
			else:
				print('YES')
		elif p < 2 * a:
			print('NO')
		elif p > a + 3 * b - 2:
			print('NO')
		else:
			print('YES')


q = int(input())
for rwer in range(q):
	(a, b) = map(int, input().split())
	s = input()
	tab = []
	count = 0
	for i in range(len(s)):
		if s[i] == '.':
			count += 1
		if s[i] == 'X':
			if count > 0:
				tab.append(count)
				count = 0
	if count > 0:
		tab.append(count)
	bat = [j for j in tab if j >= b]
	tab = bat.copy()
	if len(tab) == 0:
		print('no')
	else:
		roomb = 0
		for i in tab:
			if i >= 2 * b:
				roomb += 1
		if roomb > 1:
			print('no')
		else:
			alice = 1
			for i in tab:
				if i < a:
					alice = 0
					break
			if alice == 0:
				print('no')
			else:
				if roomb == 0:
					if len(tab) % 2 == 1:
						print('yes')
					else:
						print('no')
				if roomb == 1:
					jednostrzaly = len(tab) - 1
					duzy = max(tab)
					if duzy >= a + 4 * b - 1:
						print('no')
					else:
						if jednostrzaly % 2 == 0:
							if duzy <= a + 2 * b - 2:
								print('yes')
							elif duzy >= 3 * a:
								print('yes')
							else:
								print('no')
						if jednostrzaly % 2 == 1:
							if duzy >= 2 * a and duzy <= a + 3 * b - 2:
								print('yes')
							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()


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
		if (not (x >= b) & (x < a)) & (not x >= 2 * b) & (not (y >= b) & (y < a)) & (not y >= 2 * b):
			e = 0
			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
	if (v[0] > 0) | (v[2] > 1):
		print('NO')
	elif v[2] == 1:
		if lenght - a >= 4 * b:
			print('NO')
		elif doable(lenght, a, b, v[1] % 2) == 1:
			print('YES')
		else:
			print('NO')
	elif v[1] % 2 == 0:
		print('NO')
	else:
		print('YES')


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')
	elif ls[0] < a:
		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')