Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef has decided to start a new firm called PatentChef. However, he's stuck with some big legal issues. Their firm has received offers from a lot of companies, so Chef told his friend Junior Chef to look over some patent cases and solve them as quickly as he can.

Junior Chef is very smart and has an eye for every little detail. He quickly found a case and went ahead to solve it. The patent case is as follows:

There are N patents to be filed for a company. Chef’s firm has the first M months of the year 2018 to finish this task. (The months in a year are numbered 1 through 12.) Chef's firm has K workers (including Junior Chef) available to work on this case. Each worker can prepare exactly one patent per month.

Junior Chef assigns work to workers starting from the first month of the year. He can have any workers work on this case on any month provided that they're chosen according to the following conditions:

Each worker can only work on this patent case for at most one month.
Each worker has to work either on an even month or an odd month of the year. You are given a string S with length K and the following meaning: for each valid i, if the i-th character of S is E, worker i has to work on an even month; if it's O, this worker has to work on an odd month.
At most X workers can work on this patent case each month.

Determine whether Chef’s firm and Junior Chef can finish this patent case in time.

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains four space-separated integers N, M, X and K.
The second line contains a single string S.

------ Output ------ 

For each test case, print a single line containing the string "yes" if it's possible to finish the patent case or "no" otherwise (without quotes).

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$0 ≤ X ≤ 10^{6}$
$1 ≤ N, K ≤ 10^{6}$
$0 ≤ M ≤ 12$
$1 ≤ sum of K over all test cases ≤ 10^{7}$
$|S| = K$
$each character of S is either E or O$

------ Subtasks ------ 

Subtask #1 (20 points): 1 ≤ N ≤ M ≤ 12

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
2
4 4 2 4
EEOO
4 3 1 4
EEOO
----- Sample Output 1 ------ 
yes
no
----- explanation 1 ------ 
Example case 1: The firm can prepare 2 patents per month, so in the first month (odd), workers 3 and 4 can work on 2 patents, and in the second month (even), workers 1 and 2 can work on the remaining 2 patents.
Example case 2: There is no way for multiple workers to work on the same (even or odd) month. Hence, it's impossible to finish 4 patents in 3 months.

Difficulty: MEDIUM
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	(n, m, x, k) = map(int, input().split())
	str1_list = list(input())
	even = str1_list.count('E')
	odd = k - even
	if m % 2 == 0:
		evenOutput = min(even, x * (m // 2))
		oddOutput = min(odd, x * (m // 2))
	else:
		evenOutput = min(even, x * ((m - 1) // 2))
		oddOutput = min(odd, x * ((m - 1) // 2) + x)
	output = evenOutput + oddOutput
	if output >= n:
		print('yes')
	else:
		print('no')


import sys
R = lambda : map(int, next(sys.stdin).split())
T = int(input())
for i in range(T):
	(N, M, X, K) = R()
	S = input()
	even = 0
	odd = 0
	for i in range(K):
		if S[i] == 'E':
			even += 1
		else:
			odd += 1
	if M % 2 == 0:
		evenOutput = min(even, X * (M // 2))
		oddOutput = min(odd, X * (M // 2))
	else:
		evenOutput = min(even, X * ((M - 1) // 2))
		oddOutput = min(odd, X * ((M - 1) // 2) + X)
	output = evenOutput + oddOutput
	if output >= N:
		print('yes')
	else:
		print('no')


for _ in range(int(input())):
	(n, m, x, k) = map(int, input().split())
	s = input()
	even = s.count('E')
	odd = k - even
	even_months = m // 2
	odd_months = m - even_months
	total_even = even_months * x
	total_odd = odd_months * x
	final = min(even, total_even) + min(odd, total_odd)
	if final >= n:
		print('yes')
	else:
		print('no')


T = int(input())
for x in range(T):
	(n, m, x, k) = map(int, input().split())
	s = input()
	o_d = s.count('O')
	e_d = s.count('E')
	o_m = (m + 1) // 2
	e_m = m // 2
	p = min(x * o_m, o_d)
	y = min(x * e_m, e_d)
	if o_m * x + e_m * x < n:
		print('no')
	else:
		res = 'yes' if p + y >= n else 'no'
		print(res)


def main():
	for _ in range(int(input())):
		(N, M, X, K) = map(int, input().split(' '))
		S = input()
		odd_days = S.count('O')
		even_days = S.count('E')
		odd_months = (M + 1) // 2
		even_months = M // 2
		p = min(X * odd_months, odd_days)
		y = min(X * even_months, even_days)
		if odd_months * X + even_months * X < N:
			print('no')
		else:
			res = 'yes' if p + y >= N else 'no'
			print(res)
main()


t = int(input())
for i in range(t):
	(n, m, x, k) = map(int, input().split())
	s = input()
	o = s.count('O')
	e = s.count('E')
	odd = (m + 1) // 2
	even = m // 2
	p = min(x * odd, o)
	y = min(x * even, e)
	if x * odd + x * even < n:
		print('no')
	elif p + y >= n:
		print('yes')
	else:
		print('no')


import math
tests = int(input())
for i in range(tests):
	(n, m, x, k) = map(int, input().split())
	string = input()
	even = 0
	odd = 0
	for j in string:
		if j == 'E':
			even += 1
		elif j == 'O':
			odd += 1
	even_max = m // 2 * x
	odd_max = math.ceil(m / 2) * x
	if min(even, even_max) + min(odd, odd_max) >= n:
		print('yes')
	else:
		print('no')


from collections import Counter

def soln(n, m, x, k, s):
	counts = Counter(s)
	max_pats = 0
	for i in range(1, m + 1):
		if counts['O'] <= 0 and counts['E'] <= 0:
			break
		if i & 1:
			if counts['O'] >= x:
				counts['O'] -= x
				max_pats += x
			elif counts['O'] > 0:
				max_pats += counts['O']
				counts['O'] = 0
			else:
				continue
		elif counts['E'] >= x:
			counts['E'] -= x
			max_pats += x
		elif counts['E'] > 0:
			max_pats += counts['E']
			counts['E'] = 0
		else:
			continue
	return 'yes' if max_pats >= n else 'no'
for _ in range(int(input())):
	(n, m, x, k) = map(int, input().split())
	s = input()
	print(soln(n, m, x, k, s))


from math import gcd, sqrt, ceil, floor, log10, log2
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
RECURSION_LIMIT = int(10000000.0)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(10000000.0) + 9
NEWLINE = '\n'
SPACE = ' '
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))
enum = lambda itr, start: enumerate(itr, start)

def toposort(graph, n):
	degree = [0] * n
	for node in graph:
		for adj in graph[node]:
			degree[adj] += 1
	bfs_queue = [node for node in range(n) if not degree[node]]
	for node in bfs_queue:
		for adj in graph[node]:
			degree[adj] -= 1
			if not degree[adj]:
				bfs_queue.append(adj)
	return (bfs_queue, degree)

def dfs(graph, node, visited):
	visited.add(node)
	for adj in graph[node]:
		if adj in visited:
			continue
		dfs(graph, adj, visited)

def seive(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = is_prime[1] = False
	for i in range(2, int(n ** 0.5) + 1):
		if is_prime[i]:
			for j in range(i * i, n + 1, i):
				is_prime[j] = False
	return is_prime[n]

def solve(*args, **kwargs):
	(n, m, x, k, s) = args
	evens = s.count('E')
	odds = k - evens
	odd_months = (m + 1) // 2
	even_months = m - odd_months
	e_patents = evens if even_months * x >= evens else even_months * x
	o_patents = odds if odd_months * x >= odds else odd_months * x
	return 'yes' if n <= e_patents + o_patents else 'no'

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg1 = inp_vars(float, SPACE)
		arg3 = inp(str)
		res = solve(*(*arg1, arg3))
		if type(res) in {list, tuple, set}:
			print(*res, sep='\n')
		else:
			print(res)
main()


for _ in range(int(input())):
	(n, m, x, k) = map(int, input().split())
	s = input()
	o = s.count('O')
	e = s.count('E')
	odd = (m + 1) // 2
	even = m // 2
	odd_pa = min(x * odd, o)
	even_pa = min(x * even, e)
	if x * odd + x * even < n:
		print('no')
	elif odd_pa + even_pa >= n:
		print('yes')
	else:
		print('no')


for _ in range(int(input())):
	(n, m, x, k) = map(int, input().split())
	string1 = input()
	if k == 0 or k < n:
		print('no')
		continue
	kaam = n
	emp = k
	eval = string1.count('E')
	oval = string1.count('O')
	ww = 'odd'
	for _ in range(0, m):
		if ww == 'odd':
			kaam = kaam - min(min(oval, x), emp)
			emp = emp - min(min(oval, x), emp)
			oval -= min(min(oval, x), emp)
			ww = 'even'
		else:
			kaam = kaam - min(min(eval, x), emp)
			k = k - min(min(eval, x), emp)
			eval -= min(min(eval, x), emp)
			ww = 'odd'
	if kaam <= 0:
		print('yes')
	else:
		print('no')


for _ in range(int(input())):
	(n, m, x, k) = [int(a) for a in input().split()]
	s = input()
	e = s.count('E')
	o = s.count('O')
	if min(o, x * ((m + 1) // 2)) + min(e, x * (m // 2)) >= n:
		print('yes')
	else:
		print('no')


import math
for _ in range(int(input())):
	(n, m, x, k) = map(int, input().split())
	s = input()
	ecount = int(s.count('E'))
	ocount = int(s.count('O'))
	emonth = math.floor(m / 2)
	omonth = math.ceil(m / 2)
	if min(ocount, x * omonth) + min(ecount, x * emonth) >= n:
		print('yes')
	else:
		print('no')


for _ in range(int(input())):
	(n, m, x, k) = map(int, input().split())
	s = input()
	ec = s.count('E')
	oc = s.count('O')
	for i in range(1, m + 1):
		if i % 2 == 1:
			if oc >= x:
				oc -= x
				n -= x
			elif oc > 0:
				n -= oc
				oc = 0
		elif ec >= x:
			ec -= x
			n -= x
		elif ec > 0:
			n -= ec
			ec = 0
	if n < 1:
		print('yes')
	else:
		print('no')


t = int(input())
for _ in range(t):
	(N, M, X, K) = map(int, input().split())
	S = input()
	noOfEvenMonths = M // 2
	workersForEvenMonths = S.count('E')
	possiblePatentCompletion = min(X * noOfEvenMonths, workersForEvenMonths) + min(X * (M - noOfEvenMonths), K - workersForEvenMonths)
	if N > possiblePatentCompletion:
		print('no')
	else:
		print('yes')


for _ in range(int(input())):
	(n, m, x, k) = list(map(int, input().split()))
	s = input()
	o = s.count('O')
	e = s.count('E')
	em = m // 2
	if m % 2 == 0:
		c = m // 2
	else:
		c = m // 2 + 1
	for i in range(1, m + 1):
		if i % 2 == 0:
			if e >= x:
				e -= x
				n -= x
			else:
				n -= e
				e = 0
		elif o >= x:
			o -= x
			n -= x
		else:
			n -= o
			o = 0
	if n <= 0:
		print('yes')
	else:
		print('no')


t = int(input())
for i in range(0, t):
	(n, m, x, k) = map(int, input().split())
	s = str(input())
	o = s.count('O')
	e = k - o
	o = min(o, x * ((m + 1) // 2))
	e = min(e, x * (m // 2))
	if o + e >= n:
		print('yes')
	else:
		print('no')


for i in range(int(input())):
	(n, m, x, k) = map(int, input().split())
	p = 0
	s = input()
	ev = s.count('E')
	od = s.count('O')
	me = int(m / 2)
	mo = m - me
	if ev > x * me:
		p += x * me
	else:
		p += ev
	if od > x * mo:
		p += x * mo
	else:
		p += od
	if p >= n:
		print('yes')
	else:
		print('no')


nt = int(input())
for i in range(nt):
	numbers = list(map(int, input().split()))
	s = input()
	(n, m, x, k) = (numbers[0], numbers[1], numbers[2], numbers[3])
	if m * x < n:
		print('no')
	else:
		even_workers = s.count('E')
		odd_workers = s.count('O')
		patents_done = 0
		for month_no in range(1, m + 1):
			if month_no % 2 == 0:
				if even_workers > 0:
					val = min(x, even_workers)
					patents_done += val
					even_workers -= val
			elif odd_workers > 0:
				val_1 = min(x, odd_workers)
				patents_done += val_1
				odd_workers -= val_1
		if patents_done >= n:
			print('yes')
		else:
			print('no')


try:
	T = int(input())
	for _ in range(T):
		(n, m, x, k) = map(int, input().split())
		S = input()
		workerO = S.count('O')
		workerE = S.count('E')
		if min(workerO, x * ((m + 1) // 2)) + min(workerE, x * (m // 2)) >= n:
			print('yes')
		else:
			print('no')
except:
	pass


for i in range(int(input())):
	(n, m, x, k) = map(int, input().split())
	s = input()
	c1 = c2 = 0
	if k >= n and x * m >= n:
		for i in s:
			if i == 'E':
				c1 += 1
			if i == 'O':
				c2 += 1
		c = min(c1, x * (m // 2)) + min(c2, x * ((m + 1) // 2))
		if c >= n:
			print('yes')
		else:
			print('no')
	else:
		print('no')


for _ in range(int(input())):
	(n, m, x, k) = map(int, input().split())
	s = input()
	od = s.count('O')
	ev = s.count('E')
	evm = m // 2
	odm = m - evm
	t = 0
	if odm * x < od:
		t += odm * x
	else:
		t += od
	if evm * x < ev:
		t += evm * x
	else:
		t += ev
	if t >= n:
		print('yes')
	else:
		print('no')


for T in range(int(input())):
	(N, M, X, K) = map(int, input().split())
	S = input()
	completed = 0
	even = S.count('E')
	odd = K - even
	for month in range(M):
		if month & 1 == 0:
			w = min(odd, X)
			completed += w
			odd -= w
		else:
			w = min(even, X)
			completed += w
			even -= w
	print(['no', 'yes'][completed >= N])


t = int(input())
while t > 0:
	(n, m, x, k) = list(map(int, input().split()))
	s = input()
	first_case = m * x
	odd = s.count('O')
	even = s.count('E')
	if min(odd, x * ((m + 1) // 2)) + min(even, x * (m // 2)) >= n:
		print('yes')
	else:
		print('no')
	t -= 1


t = int(input())
for _ in range(t):
	(n, m, x, k) = map(int, input().split())
	arr = input()
	even = arr.count('E')
	odd = arr.count('O')
	casesSolved = 0
	i = 0
	flag = 0
	while i < m:
		if i % 2 == 0:
			if x >= odd and odd > 0:
				n = n - odd
				odd = 0
			elif x < odd:
				n = n - x
				odd = odd - x
		elif x >= even and even > 0:
			n = n - even
			even = 0
		elif x < even:
			n = n - x
			even = even - x
		if n <= 0:
			flag = 1
			break
		i = i + 1
	if flag == 0:
		print('no')
	else:
		print('yes')


for _ in range(int(input())):
	(n, m, x, k) = [int(y) for y in input().split()]
	i = input()
	e = i.count('E')
	o = k - e
	li = False
	l = 0
	for s in range(1, m + 1):
		if s % 2 == 1 and o > 0:
			if o >= x:
				l += x
				o -= x
			else:
				l += o
				o = 0
		if s % 2 == 0 and e > 0:
			if e >= x:
				l += x
				e -= x
			else:
				l += e
				e = 0
		if l >= n:
			li = True
			break
	if li:
		print('yes')
	else:
		print('no')


t = int(input())
for U in range(t):
	(n, m, x, k) = [int(i) for i in input().split()]
	s = input().rstrip('\r')
	odd = 0
	even = 0
	for i in s:
		if i == 'E':
			even += 1
		else:
			odd += 1
	if x == 0:
		print('no')
	else:
		finans = 0
		for ii in range(0, m):
			ans = 0
			ans1 = 0
			if ii % 2 == 0:
				if x >= odd:
					ans += odd
				else:
					ans += x
				odd = odd - ans
				finans += ans
			else:
				if x >= even:
					ans1 += even
				else:
					ans1 += x
				even = even - ans1
				finans += ans1
		if finans >= n:
			print('yes')
		else:
			print('no')


try:
	T = int(input())
	for t in range(T):
		arr = [int(x) for x in input().split()]
		N = arr[0]
		M = arr[1]
		X = arr[2]
		K = arr[3]
		S = input()
		eve = S.count('E')
		odd = S.count('O')
		for i in range(1, M + 1):
			if N <= 0 or (eve == 0 and odd == 0):
				break
			if i % 2 == 0:
				if eve - X >= 0:
					N -= X
					eve -= X
				else:
					N -= eve
					eve = 0
			elif odd - X >= 0:
				N -= X
				odd -= X
			else:
				N -= odd
				odd = 0
		if N <= 0:
			print('yes')
		else:
			print('no')
except:
	print('Hello')


for t in range(int(input())):
	(n, m, x, k) = map(int, input().split())
	S = input()
	em = m // 2
	om = (m + 1) // 2
	e = min(S.count('E'), x * em)
	o = min(S.count('O'), x * om)
	print('yes' if e + o >= n else 'no')


for _ in range(int(input())):
	l = list(map(int, input().split(' ')))
	s = input()
	e = s.count('E')
	o = s.count('O')
	i = 0
	if e > l[1] // 2 * l[2]:
		i += l[1] // 2 * l[2]
	else:
		i += e
	if l[1] % 2 == 1:
		if o > (l[1] // 2 + 1) * l[2]:
			i += (l[1] // 2 + 1) * l[2]
		else:
			i += o
	elif o > l[1] // 2 * l[2]:
		i += l[1] // 2 * l[2]
	else:
		i += o
	if i >= l[0]:
		print('yes')
	else:
		print('no')


t = int(input())
for _ in range(t):
	(N, m, x, k) = map(int, input().split())
	s = input()
	e = s.count('E')
	o = k - e
	n = 0
	for months in range(1, m + 1):
		if months % 2 != 0:
			if o < x:
				n += o
				o = 0
			else:
				o -= x
				n += x
		elif e < x:
			n += e
			e = 0
		else:
			e -= x
			n += x
	if n < N:
		print('no')
	else:
		print('yes')


t = int(input())
for _ in range(t):
	(N, M, X, K) = map(int, input().split())
	s = input()
	e = s.count('E')
	o = K - e
	n = 0
	for i in range(1, M + 1):
		if i % 2 != 0:
			if X < o:
				fstm = X
			else:
				fstm = o
			o -= fstm
			n += fstm
		else:
			if X < e:
				sndm = X
			else:
				sndm = e
			e -= sndm
			n += sndm
	if n >= N:
		print('yes')
	else:
		print('no')


import collections
t = int(input())
while t > 0:
	t -= 1
	(n, m, x, k) = map(int, input().split())
	s = input()
	count = collections.Counter(s)
	ecount = count['E']
	ocount = count['O']
	patents = 0
	for i in range(1, m + 1):
		if i & 1:
			ans = min(x, ocount)
			ocount -= ans
			patents += ans
		else:
			ans = min(x, ecount)
			ecount -= ans
			patents += ans
	print('yes') if patents >= n else print('no')


t = int(input())
for i in range(t):
	(n, m, x, k) = [int(x) for x in input().split(' ')]
	s = input()
	even = 0
	odd = 0
	for character in s:
		if character == 'E':
			even = even + 1
		elif character == 'O':
			odd = odd + 1
	even_months = m // 2
	odd_months = (m + 1) // 2
	total = min(even_months * x, even) + min(odd_months * x, odd)
	if total < n:
		print('no')
	else:
		print('yes')


def getPatent(N, M, X, K, E, O):
	maxPatent = 0
	TE = E
	TO = O
	for i in range(1, M + 1):
		if TO == 0 and TE == 0:
			break
		if i % 2:
			if TO:
				maxPatent = maxPatent + min(X, TO)
				TO = TO - min(X, TO)
		elif TE:
			maxPatent = maxPatent + min(X, TE)
			TE = TE - min(X, TE)
	if maxPatent >= N:
		print('yes')
	else:
		print('no')
for i in range(int(input())):
	myList = list(map(int, input().split()))
	workers = list(input())
	E = workers.count('E')
	O = workers.count('O')
	getPatent(*myList, E, O)


t = int(input())
for _ in range(t):
	(n, m, x, k) = map(int, input().split())
	s = input()
	(ec, oc) = (0, 0)
	for i in range(k):
		if s[i] == 'E':
			ec += 1
		else:
			oc += 1
	if m % 2 == 0:
		(me, mo) = (m // 2, m // 2)
	else:
		(me, mo) = (m // 2, m // 2 + 1)
	c = 0
	if min(oc, x * mo) + min(ec, x * me) >= n:
		print('yes')
	else:
		print('no')


t = int(input())
while t > 0:
	(n, m, x, k) = [int(i) for i in input().split()]
	s = list(str(input()))
	odd = s.count('O')
	even = s.count('E')
	for i in range(1, m + 1):
		if n == 0 or (even == 0 and odd == 0):
			break
		if i % 2 == 0:
			if even >= x:
				n -= x
				even -= x
			else:
				n -= even
				even = 0
		elif odd >= x:
			n -= x
			odd -= x
		else:
			n -= odd
			odd = 0
	if n <= 0:
		print('yes')
	else:
		print('no')
	t -= 1


for _ in range(int(input())):
	(n, m, x, k) = map(int, input('').split())
	s = input()
	ev = s.count('E')
	od = s.count('O')
	e = int(m / 2)
	o = m - e
	val = min(x * e, ev) + min(x * o, od)
	if val >= n:
		print('yes')
	else:
		print('no')


import sys
T = int(input())
for t in range(T):
	input_str = input()
	(n, m, x, k) = [int(v) for v in input_str.split(' ')]
	odd_even = input()
	odd_count = odd_even.count('O')
	even_count = odd_even.count('E')
	for i in range(1, m + 1):
		if i % 2 == 1:
			if odd_count >= x:
				n -= x
				odd_count -= x
			else:
				n -= odd_count
				odd_count = 0
		elif even_count >= x:
			n -= x
			even_count -= x
		else:
			n -= even_count
			even_count = 0
	if n <= 0:
		print('yes')
	else:
		print('no')


import sys
T = int(input())
for z in range(T):
	input_str = input()
	(n, m, x, k) = [int(i) for i in input_str.split(' ')]
	s = input()
	even_count = s.count('E')
	odd_count = s.count('O')
	for c in range(1, m + 1):
		if not c % 2 == 0:
			if odd_count >= x:
				n -= x
				odd_count -= x
			else:
				n -= odd_count
				odd_count = 0
		elif even_count >= x:
			n -= x
			even_count -= x
		else:
			n -= even_count
			even_count = 0
	if n <= 0:
		print('yes')
	else:
		print('no')


t = int(input())
for z in range(t):
	(n, m, x, k) = map(int, input().split())
	s = input()
	e = s.count('E')
	o = s.count('O')
	ev = 0
	od = 0
	for i in range(1, m + 1):
		if i % 2 == 0:
			ev += 1
		else:
			od += 1
	val = min(ev * x, e) + min(od * x, o)
	if val >= n:
		print('yes')
	else:
		print('no')


import sys
test = int(input())
for z in range(test):
	temp = input()
	(n, m, x, k) = [int(i) for i in temp.split(' ')]
	s = input()
	ewc = s.count('E')
	owc = s.count('O')
	em = int(m / 2)
	if not m % 2 == 0:
		om = int(m / 2) + 1
	else:
		om = int(m / 2)
	for c in range(1, m + 1):
		if not c % 2 == 0:
			if owc >= x:
				n -= x
				owc -= x
			else:
				n -= owc
				owc = 0
		elif ewc >= x:
			n -= x
			ewc -= x
		else:
			n -= ewc
			ewc = 0
	if n <= 0:
		print('yes')
	else:
		print('no')


t = int(input())
while t != 0:
	(m, n, x, k) = [int(x) for x in input().split()]
	str = input()
	leng = len(str)
	p = 0
	even = 0
	odd = 0
	while p < leng:
		if p < leng:
			if str[p] == 'E':
				even = even + 1
			elif str[p] == 'O':
				odd = odd + 1
		p = p + 1
	month = n
	patent = m
	i = 1
	while month != 0 and patent > 0:
		if i % 2 != 0:
			if odd >= x and odd != 0:
				odd = odd - x
				patent = patent - x
			elif odd < x and odd != 0:
				patent = patent - odd
				odd = 0
		elif i % 2 == 0:
			if even >= x and even != 0:
				even = even - x
				patent = patent - x
			elif even < x and even != 0:
				patent = patent - even
				even = 0
		month = month - 1
		i = i + 1
	if patent <= 0:
		print('yes')
	else:
		print('no')
	t = t - 1


q = int(input())
for qq in range(q):
	(n, m, x, k) = [int(i) for i in input().split()]
	s = input()
	A = 0
	B = 0
	for c in s:
		if c == 'E':
			A += 1
		elif c == 'O':
			B += 1
	Ne = m // 2
	No = (m + 1) // 2
	maxx = min(Ne * x, A) + min(No * x, B)
	if maxx >= n:
		print('yes')
	else:
		print('no')


for i in range(int(input())):
	(n, m, x, k) = map(int, input().strip().split(' '))
	s = input()
	ec = oc = p = 0
	for i in range(k):
		if s[i] == 'E':
			ec += 1
		elif s[i] == 'O':
			oc += 1
	for i in range(m):
		if i % 2 == 0:
			t = min(oc, x)
			p += t
			oc -= t
		else:
			t = min(ec, x)
			p += t
			ec -= t
		if p > n:
			break
	if p >= n:
		print('yes')
	else:
		print('no')


for _ in range(int(input())):
	(n, m, x, k) = tuple(map(int, input().split()))
	s = input().strip()
	(o_count, e_count) = (s.count('O'), s.count('E'))
	for i in range(1, m + 1):
		if i & 1:
			work = min(x, o_count)
			o_count -= work
			n -= work
		else:
			work = min(x, e_count)
			e_count -= work
			n -= work
	print('no') if n > 0 else print('yes')


t = int(input())
while t > 0:
	(n, m, x, k) = map(int, input().split())
	a = input()
	even = 0
	odd = 0
	months = 1
	for i in range(k):
		if a[i] == 'E':
			even += 1
		else:
			odd += 1
	while n > 0 and months <= m:
		if months % 2 != 0:
			if odd >= x:
				n -= x
				odd -= x
			else:
				n -= odd
				odd = 0
		elif even >= x:
			n -= x
			even -= x
		else:
			n -= even
			even = 0
		months += 1
	if n <= 0:
		print('yes')
	else:
		print('no')
	t = t - 1


for _ in range(int(input())):
	(pat, mon, Xw, Kw) = map(int, input().split())
	string = input()
	Ework = string.count('E')
	Owork = string.count('O')
	for i in range(1, mon + 1):
		if pat > 0 and Kw > 0:
			if Ework >= Xw and Owork >= Xw:
				if i % 2 == 0:
					pat = pat - Xw
					Ework -= Xw
				elif i % 2 != 0:
					pat = pat - Xw
					Owork -= Xw
				Kw -= Xw
			elif Ework >= Xw and Owork < Xw:
				if i % 2 == 0:
					pat = pat - Xw
					Ework -= Xw
					Kw -= Xw
				elif i % 2 != 0:
					pat = pat - Owork
					Kw -= Owork
					Owork -= Owork
			elif Ework < Xw and Owork >= Xw:
				if i % 2 == 0:
					pat = pat - Ework
					Kw -= Ework
					Ework -= Ework
				elif i % 2 != 0:
					pat = pat - Xw
					Owork -= Xw
					Kw -= Xw
			elif Ework < Xw or Owork < Xw:
				if i % 2 == 0:
					pat = pat - Ework
					Kw -= Ework
					Ework -= Ework
				elif i % 2 != 0:
					pat = pat - Owork
					Kw -= Owork
					Owork -= Owork
	if pat <= 0:
		print('yes')
	else:
		print('no')


from collections import Counter
t = int(input())
for w in range(t):
	(n, m, x, k) = list(map(int, input().split()))
	s = Counter(input())
	e = s['E']
	o = s['O']
	try:
		if n / m <= float(x):
			for i in range(1, m + 1, 2):
				if x <= o and n > 0:
					n -= x
					o -= x
				else:
					n -= o
					o = 0
					break
			if n > 0 and m >= 2:
				for j in range(2, m + 1, 2):
					if x <= e and n > 0:
						n -= x
						e -= x
					else:
						n -= e
						e = 0
						break
			if n <= 0:
				print('yes')
			else:
				print('no')
		else:
			print('no')
	except:
		print('no')


T = int(input())
for _ in range(T):
	(N, M, X, K) = (int(i) for i in input().split())
	s = input()
	E = s.count('E')
	O = K - E
	em = M // 2
	om = M - em
	if min(X * em, E) + min(om * X, O) >= N:
		print('yes')
	else:
		print('no')


T = int(input())
while T > 0:
	(N, M, X, K) = map(int, input().split())
	d = input().strip()
	S = []
	even = 0
	odd = 0
	for i in range(len(d)):
		if d[i] == 'E':
			even = even + 1
		else:
			odd = odd + 1
	month_even = M // 2
	month_odd = M - month_even
	if M * X < N:
		print('no')
	elif K < N:
		print('no')
	elif K > N:
		for j in range(1, M + 1):
			if j % 2 == 1:
				if odd == 0:
					month_odd -= 1
					if N == 0:
						break
				elif odd >= X:
					month_odd -= 1
					odd = odd - X
					N = N - X
					if N == 0:
						break
				elif odd < X:
					month_odd -= 1
					N = N - odd
					odd = 0
					if N == 0:
						break
			elif j % 2 == 0:
				if even == 0:
					month_even -= 1
					if N == 0:
						break
				elif even >= X:
					month_even -= 1
					even = even - X
					N = N - X
					if N == 0:
						break
				elif even < X:
					month_even -= 1
					N = N - even
					even = 0
					if N == 0:
						break
		if N > 0:
			print('no')
		else:
			print('yes')
	elif month_even < even / X or month_odd < odd / X:
		print('no')
	else:
		print('yes')
	T -= 1


for i in range(int(input())):
	(n, m, x, k) = map(int, input().split())
	str = input()
	we = 0
	wo = 0
	flag = 0
	count = 0
	for j in range(k):
		if str[j] == 'E':
			we += 1
		else:
			wo += 1
	if m % 2 == 0:
		mo = m // 2
		me = mo
	else:
		me = m // 2
		mo = me + 1
	if k >= n:
		for j in range(m):
			if j % 2 != 0:
				if we >= x:
					pwe = x
					we -= pwe
				else:
					pwe = we
					we -= pwe
				count += pwe
			else:
				if wo >= x:
					pwo = x
					wo -= pwo
				else:
					pwo = wo
					wo -= pwo
				count += pwo
		if count >= n:
			print('yes')
		else:
			print('no')
	else:
		print('no')


t = int(input())
while t:
	x = list(map(int, input().split()))
	s = input()
	if x[1] * x[2] < x[0]:
		print('no')
	else:
		a = x[1] // 2
		b = x[1] - a
		m = s.count('E')
		n = s.count('O')
		p = 0
		if m <= x[2]:
			if a != 0:
				p = p + m
		elif m // x[2] >= a:
			p = p + x[2] * a
		else:
			p = p + m
		if n <= x[2]:
			p = p + n
		elif n // x[2] >= b:
			p = p + x[2] * b
		else:
			p = p + n
		if p >= x[0]:
			print('yes')
		else:
			print('no')
	t = t - 1


from collections import Counter

def answer(s, n, m, x, k):
	counts = Counter(s)
	state = True
	patents = n
	for i in range(m):
		sub = x if x <= patents else patents
		if state == True:
			if counts['O'] < sub:
				sub = counts['O']
			counts['O'] -= sub
		else:
			if counts['E'] < sub:
				sub = counts['E']
			counts['E'] -= sub
		patents -= sub
		state = not state
	if patents > 0:
		return 'no'
	return 'yes'
t = int(input())
for _ in range(t):
	(n, m, x, k) = list(map(int, input().strip().split()))
	s = input().strip()
	print(answer(s, n, m, x, k))


import sys
tc = int(input())
while tc:
	tc -= 1
	(n, m, x, k) = map(int, sys.stdin.readline().split())
	s = input()
	ce = 0
	co = 0
	for i in range(k):
		if s[i] == 'E':
			ce += 1
		elif s[i] == 'O':
			co += 1
	for i in range(1, m + 1):
		if i % 2 == 0:
			patthismonth = min(ce, x)
			ce -= patthismonth
			n -= patthismonth
		else:
			patthismonth = min(co, x)
			co -= patthismonth
			n -= patthismonth
	if n <= 0:
		print('yes')
	else:
		print('no')


for _ in range(int(input())):
	(N, m, x, k) = map(int, input().split())
	sr = input()
	p = 0
	if m * x < N:
		print('no')
	else:
		evwrk = sr.count('E')
		odwrk = sr.count('O')
		evmn = m // 2
		odmn = m - evmn
		if evwrk <= x:
			if evmn != 0:
				p = p + evwrk
		elif evwrk // x >= evmn:
			p = p + evmn * x
		else:
			p = p + evwrk
		if odwrk <= x:
			p = p + odwrk
		elif odwrk // x >= odmn:
			p = p + odmn * x
		else:
			p = p + odwrk
		if p >= N:
			print('yes')
		else:
			print('no')


t = int(input())
for i in range(0, t):
	(N, M, X, K) = map(int, input().split())
	s = input().strip()
	even = 0
	odd = 0
	for item in s:
		if item == 'E':
			even += 1
		else:
			odd += 1
	T = 0
	for i in range(1, M + 1):
		if i % 2 == 0:
			if even >= X:
				T += X
				even -= X
			else:
				T += even
				even = 0
		elif odd >= X:
			T += X
			odd -= X
		else:
			T += odd
			odd = 0
	if T >= N:
		print('yes')
	else:
		print('no')


t = int(input())
while t:
	t = t - 1
	(n, m, x, k) = map(int, input().split())
	s = input()
	p = 0
	if m * x < n:
		print('no')
	else:
		ew = s.count('E')
		ow = s.count('O')
		em = m // 2
		om = m - em
		if ew <= x:
			if em != 0:
				p = p + ew
		elif ew // x >= em:
			p = p + em * x
		else:
			p = p + ew
		if ow <= x:
			p = p + ow
		elif ow // x >= om:
			p = p + om * x
		else:
			p = p + ow
		if p >= n:
			print('yes')
		else:
			print('no')


for a in range(int(input())):
	l = list(map(int, input().split(' ')))
	n = l[0]
	m = l[1]
	x = l[2]
	k = l[3]
	s = input()
	noe = 0
	noo = 0
	for i in range(k):
		if s[i] == 'E':
			noe += 1
		else:
			noo += 1
	for i in range(m):
		if (i + 1) % 2 == 1:
			if x < noo:
				noo -= x
				n -= x
			else:
				n -= noo
				noo = 0
		elif x < noe:
			noe -= x
			n -= x
		else:
			n -= noe
			noe = 0
	if n <= 0:
		print('yes')
	else:
		print('no')


for i in range(int(input())):
	l = [int(j) for j in input().split()]
	s = input()
	(n, d, a, w) = (l[0], l[1], l[2], l[3])
	even = s.count('E')
	odd = s.count('O')
	for k in range(1, d + 1):
		if k % 2 != 0:
			if odd >= a and odd > 0:
				n = n - a
				odd = odd - a
			elif odd <= a and odd > 0:
				n = n - odd
				odd = 0
		elif even >= a and even > 0:
			n = n - a
			even = even - a
		elif even <= a and even > 0:
			n = n - even
			even = 0
	if n <= 0:
		print('yes')
	else:
		print('no')


for i in range(int(input())):
	(n, m, x, k) = map(int, input().split())
	l = list(input())
	even = l.count('E')
	odd = l.count('O')
	flag = 0
	for j in range(1, m + 1):
		if j % 2 != 0:
			min_odd = min(odd, x)
			n = n - min_odd
			odd = odd - min_odd
		if j % 2 == 0:
			min_even = min(even, x)
			n = n - min_even
			even = even - min_even
		if n <= 0:
			flag = 1
			break
	if flag == 1:
		print('yes')
	else:
		print('no')