A company conducted a coding test to hire candidates. $N$ candidates appeared for the test, and each of them faced $M$ problems. Each problem was either unsolved by a candidate (denoted by 'U'), solved partially (denoted by 'P'), or solved completely (denoted by 'F'). 

To pass the test, each candidate needs to either solve $X$ or more problems completely, or solve $(X-1)$ problems completely, and $Y$ or more problems partially.

Given the above specifications as input, print a line containing $N$ integers. The $i^{th}$ integer should be $1$ if the $i^{th}$ candidate has passed the test, else it should be $0$.

------ Input: ------

The first line of the input contains an integer $T$, denoting the number of test cases.
The first line of each test case contains two space-separated integers, $N$ and $M$, denoting the number of candidates who appeared for the test, and the number of problems in the test, respectively.
The second line of each test case contains two space-separated integers, $X$ and $Y$, as described above, respectively.
The next $N$ lines contain $M$ characters each. The $j^{th}$ character of the $i^{th}$ line denotes the result of the $i^{th}$ candidate in the $j^{th}$ problem. 'F' denotes that the problem was solved completely, 'P' denotes partial solve, and 'U' denotes that the problem was not solved by the candidate.

------ Output: ------

For each test case, print a single line containing $N$ integers. The $i^{th}$  integer denotes the result of the $i^{th}$ candidate. $1$ denotes that the candidate passed the test, while $0$ denotes that he/she failed the test.

------ Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$
$2 ≤ M ≤ 100$
$1 ≤ X, Y ≤ M$
$1 ≤ (X-1)+Y ≤ M$

----- Sample Input 1 ------ 
3

4 5

3 2

FUFFP

PFPFU

UPFFU

PPPFP

3 4

1 3

PUPP

UUUU

UFUU

1 3

2 2

PPP
----- Sample Output 1 ------ 
1100

101

0
----- explanation 1 ------ 
- Sample Test 1: There are $4$ candidates and $5$ problems. Each candidate needs to solve $3$ or more problems completely, or $2$ problems completely and $2$ or more problems partially. Only the first and the second candidates satisfy this.

- Sample Test 2: The candidates need to either solve at least one problem completely, or they need to solve three or more problems partially. Only candidates $1$ and $3$ satisfy this.

- Sample Test 3: The candidate needs to either solve two or more problems completely, or solve at least one problems completely and two problems partially. The candidate does not satisfy this.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Data structures

Implementation


Solutions:
T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	(X, Y) = map(int, input().split())
	string = []
	for i in range(N):
		s = input()
		string.append(s)
	ans = ''
	for i in string:
		P = i.count('P')
		F = i.count('F')
		if F >= X or (F >= X - 1 and P >= Y):
			ans += '1'
		else:
			ans += '0'
	print(ans)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	(x, y) = map(int, input().split())
	l = []
	s = ''
	for i in range(a):
		l.append(input())
	for i in l:
		if i.count('F') >= x or (i.count('F') >= x - 1 and i.count('P') >= y):
			s += '1'
		else:
			s += '0'
	print(s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	ans = ''
	for i in range(0, n):
		s = input()
		f = s.count('F')
		p = s.count('P')
		if f >= x or (f >= x - 1 and p >= y):
			ans += '1'
		else:
			ans += '0'
	print(ans)


for _ in range(0, int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	l = []
	s = []
	f = 0
	p = 0
	for i in range(0, n):
		l.append(input())
	for i in l:
		f = 0
		p = 0
		for j in i:
			if j == 'F':
				f = f + 1
			if j == 'P':
				p = p + 1
		if f >= x or (f == x - 1 and p >= y):
			s.append('1')
		else:
			s.append('0')
	print(''.join(s))


for _ in range(int(input())):
	(students, problems) = map(int, input().split())
	(complete, partially) = map(int, input().split())
	lst = []
	for i in range(students):
		x = str(input())
		(result, result1) = (0, 0)
		for j in x:
			if j == 'F':
				result = result + 1
			elif j == 'P':
				result1 = result1 + 1
		if result >= complete or (result >= complete - 1 and result1 >= partially):
			lst.append('1')
		else:
			lst.append('0')
	print(''.join(lst))


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	while n:
		n -= 1
		data = input()
		cpass = data.count('F')
		ppass = data.count('P')
		if cpass >= x or (cpass >= x - 1 and ppass >= y):
			print(1, end='')
		else:
			print(0, end='')
	print()


for i in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	result = ''
	for i in range(n):
		s = input()
		F = s.count('F')
		P = s.count('P')
		U = s.count('U')
		if F >= x or (F == x - 1 and P >= y):
			result = result + '1'
		else:
			result = result + '0'
	print(result)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	r = ''
	for i in range(n):
		s = input()
		if s.count('F') >= x:
			r = r + '1'
		elif s.count('F') == x - 1 and s.count('P') >= y:
			r = r + '1'
		else:
			r = r + '0'
	print(r)


for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	(x, y) = map(int, input().strip().split())
	test = [0 for _ in range(n)]
	for i in range(n):
		test[i] = input()
	for s in test:
		full = 0
		partial = 0
		for i in s:
			if i == 'F':
				full += 1
			elif i == 'P':
				partial += 1
		if full >= x or (full == x - 1 and partial >= y):
			print(1, end='')
		else:
			print(0, end='')
	print()


t = int(input())
while t > 0:
	(n, m) = input().split()
	(n, m) = [int(n), int(m)]
	(x, y) = input().split()
	(x, y) = [int(x), int(y)]
	while n > 0:
		s = input()
		c_f = c_p = 0
		for i in range(m):
			if s[i] == 'F':
				c_f = c_f + 1
			if s[i] == 'P':
				c_p = c_p + 1
		if c_f >= x:
			print(1, end='')
		elif c_f == x - 1 and c_p >= y:
			print(1, end='')
		else:
			print(0, end='')
		n = n - 1
	print()
	t = t - 1


for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	(x, y) = map(int, input().split())
	s = ' '
	for i in range(n):
		k = input()
		f = k.count('F')
		p = k.count('P')
		u = k.count('U')
		if f >= x or (f == x - 1 and p >= y):
			s = s + '1'
		else:
			s = s + '0'
	print(s)


for tc in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	ans = ''
	for i in range(n):
		(com, par) = (0, 0)
		rep = input()
		for char in rep:
			if char == 'F':
				com += 1
			if char == 'P':
				par += 1
		if com >= x:
			ans += '1'
		elif com == x - 1 and par >= y:
			ans += '1'
		else:
			ans += '0'
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	str = ''
	for i in range(n):
		f_c = 0
		p_c = 0
		u_c = 0
		s = input()
		for i in s:
			if i == 'F':
				f_c = f_c + 1
			elif i == 'P':
				p_c = p_c + 1
			else:
				u_c = u_c + 1
		if f_c >= x:
			str = str + '1'
		elif f_c >= x - 1 and p_c >= y:
			str = str + '1'
		else:
			str = str + '0'
	print(str)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	d = ''
	for i in range(n):
		s = input()
		q = s.count('P')
		v = s.count('U')
		g = s.count('F')
		if g >= x or (g >= x - 1 and q >= y):
			d += '1'
		else:
			d += '0'
	print(d)


t = int(input())
for tc in range(t):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	d = ''
	for j in range(n):
		s = input()
		a = s.count('F')
		b = s.count('P')
		c = s.count('U')
		if a >= x or (a >= x - 1 and b >= y):
			d += '1'
		else:
			d += '0'
	print(d)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	pas = ''
	for i in range(n):
		score = input()
		if score.count('F') >= x or (score.count('F') == x - 1 and score.count('P') >= y):
			pas += '1'
		else:
			pas += '0'
	print(pas)


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	(x, y) = map(int, input().split(' '))
	final = ''
	for i in range(n):
		a = input()
		p = False
		if a.count('F') >= x or (a.count('F') == x - 1 and a.count('P') >= y):
			p = True
		if p:
			final += '1'
		else:
			final += '0'
	print(final)


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	(X, Y) = map(int, input().split())
	result = []
	for i in range(N):
		remarks = str(input())
		(F, P) = (0, 0)
		for marks in remarks:
			if marks == 'F':
				F += 1
			elif marks == 'P':
				P += 1
		if F >= X or (F == X - 1 and P >= Y):
			result.append('1')
		else:
			result.append('0')
	print(''.join(result))


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	(X, Y) = map(int, input().split())
	listt = []
	for i in range(N):
		Z = str(input())
		solved = 0
		partialy_solved = 0
		for i in Z:
			if i == 'F':
				solved = solved + 1
			elif i == 'P':
				partialy_solved = partialy_solved + 1
		if solved >= X or (solved == X - 1 and partialy_solved >= Y):
			listt.append('1')
		else:
			listt.append('0')
	print(''.join(listt))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	ans = ''
	for i in range(n):
		marksheet = input()
		fully_solved = marksheet.count('F')
		part_solved = marksheet.count('P')
		if fully_solved >= x or (fully_solved == x - 1 and part_solved >= y):
			ans += '1'
		else:
			ans += '0'
	print(ans)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	s1 = ''
	for j in range(n):
		s = input()
		a = s.count('F')
		b = s.count('P')
		if a >= x or (a == x - 1 and b >= y):
			s1 += '1'
		else:
			s1 += '0'
	print(s1)


for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	(X, Y) = list(map(int, input().split()))
	passList = []
	for i in range(N):
		resultStr = input()
		countF = 0
		countP = 0
		for letter in resultStr:
			if letter == 'F':
				countF += 1
			elif letter == 'P':
				countP += 1
		if countF >= X or (countF == X - 1 and countP >= Y):
			passList.append('1')
		else:
			passList.append('0')
	print(''.join(passList))


for t in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	for i in range(n):
		s = input()
		(a, b) = (0, 0)
		for j in s:
			if j == 'F':
				a += 1
			elif j == 'P':
				b += 1
			if a >= x or (a == x - 1 and b >= y):
				print(1, end='')
				break
		else:
			print(0, end='')
	print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	l = []
	for i in range(n):
		s = input()
		a = s.count('P')
		b = s.count('F')
		if b >= x:
			l.append('1')
		elif b == x - 1 and a >= y:
			l.append('1')
		else:
			l.append('0')
	print(''.join(l))


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	(X, Y) = map(int, input().split())
	P = []
	for j in range(N):
		S = input()
		P1 = S.count('F')
		P2 = S.count('P')
		P3 = S.count('U')
		if P1 >= X:
			P.append('1')
		elif P1 == X - 1 and P2 >= Y:
			P.append('1')
		else:
			P.append('0')
	print(''.join(P))


t = int(input())
for I in range(t):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	for j in range(n):
		line = input()
		cnt_f = 0
		cnt_p = 0
		for char in line:
			if char == 'F':
				cnt_f += 1
			if char == 'P':
				cnt_p += 1
		if cnt_f >= x or (cnt_f >= x - 1 and cnt_p >= y):
			print(1, end='')
		else:
			print(0, end='')
	print()


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(c, d) = map(int, input().split())
	w = ''
	for i in range(a):
		x = list(input())
		if x.count('F') >= c or (x.count('F') == c - 1 and x.count('P') >= d):
			w += '1'
		else:
			w += '0'
	print(w)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	for i in range(n):
		st = input()
		c = 0
		p = 0
		u = 0
		for i in st:
			if i == 'F':
				c += 1
			elif i == 'P':
				p += 1
			else:
				u += 1
			if c >= x or (c == x - 1 and p >= y):
				print(1, end='')
				break
		else:
			print(0, end='')
	print()


t = int(input())
for u in range(t):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	for j in range(n):
		s = input()
		l = ''
		for i in range(n):
			if s.count('F') >= x or (s.count('F') == x - 1 and s.count('P') >= y):
				l += '1'
				break
			else:
				l += '0'
				break
		print(l, end='')
	print()


for t in range(int(input())):
	(c, p) = map(int, input().split())
	(nc, np) = map(int, input().split())
	ans = ''
	for k in range(c):
		s = input()
		pc = 0
		cc = 0
		for i in range(p):
			if s[i] == 'F':
				cc += 1
			elif s[i] == 'P':
				pc += 1
		if cc >= nc:
			ans = ans + '1'
		elif cc == nc - 1 and pc >= np:
			ans = ans + '1'
		else:
			ans = ans + '0'
	print(ans)


q = int(input())
while q > 0:
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	r = ''
	for i in range(n):
		l = input()
		l = list(l)
		f = l.count('F')
		p = l.count('P')
		if f >= x:
			r = r + '1'
		elif f == x - 1 and p >= y:
			r = r + '1'
		else:
			r = r + '0'
	print(r)
	q = q - 1


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	l = []
	for i in range(n):
		a = input()
		f = 0
		p = 0
		u = 0
		for i in range(len(a)):
			if a[i] == 'F':
				f += 1
			elif a[i] == 'P':
				p += 1
			elif a[i] == 'U':
				u += 1
		if f >= x:
			l.append(1)
		elif f == x - 1 and p >= y:
			l.append(1)
		else:
			l.append(0)
	for j in l:
		print(j, end='')
	print()


for i in range(0, int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	ans = ''
	for i in range(0, n):
		s = input()
		(cntF, cntP) = (0, 0)
		for i in range(0, m):
			if s[i] == 'F':
				cntF += 1
			elif s[i] == 'P':
				cntP += 1
		if cntF >= x or (cntF == x - 1 and cntP >= y):
			ans = ans + '1'
		else:
			ans = ans + '0'
	print(ans)


for i in range(int(input())):
	(n, m) = map(int, input().strip().split())
	(x, y) = map(int, input().strip().split())
	st = ''
	for j in range(n):
		s = input()
		u = 0
		f = 0
		p = 0
		for i in s:
			if i == 'U':
				u += 1
			elif i == 'F':
				f += 1
			elif i == 'P':
				p += 1
		if f >= x:
			st += '1'
		elif f == x - 1 and p >= y:
			st += '1'
		else:
			st += '0'
	print(st)


for i in range(int(input())):
	(n, m) = map(int, input().split(' '))
	(x, y) = map(int, input().split(' '))
	abc1 = ''
	for a in range(n):
		abc = input()
		if abc.count('F') >= x:
			abc1 += '1'
		elif abc.count('F') == x - 1 and abc.count('P') >= y:
			abc1 += '1'
		else:
			abc1 += '0'
	print(abc1)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	for i in range(n):
		s = input()
		fc = s.count('F')
		pc = s.count('P')
		if fc >= x or (fc == x - 1 and pc >= y):
			print(1, end='')
		else:
			print(0, end='')
	print('')


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	(a, b) = map(int, input().split())
	c = []
	for i in range(x):
		t = str(input())
		P = t.count('P')
		F = t.count('F')
		if F >= a - 1:
			if F > a - 1:
				c.append(1)
			elif P >= b:
				c.append(1)
			else:
				c.append(0)
		else:
			c.append(0)
	for j in c:
		print(j, end='')
	print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	ans = ''
	for i in range(n):
		s = input()
		solved = 0
		partial = 0
		for i in s:
			if i == 'F':
				solved += 1
			elif i == 'P':
				partial += 1
		if solved >= x or (solved == x - 1 and partial >= y):
			ans += '1'
		else:
			ans += '0'
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	ans = ''
	for i in range(n):
		s = input()
		a = s.count('F') >= x
		b = s.count('F') >= x - 1
		c = s.count('P') >= y
		e = b and c
		if a or e:
			ans += '1'
		else:
			ans += '0'
	print(ans)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	(x, y) = [int(x) for x in input().split()]
	res = ''
	for i in range(n):
		case = input()
		if case.count('F') >= x or (case.count('F') == x - 1 and case.count('P') >= y):
			res += '1'
		else:
			res += '0'
	print(res)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	st = ''
	for j in range(n):
		s = str(input())
		full = s.count('F')
		part = s.count('P')
		if full >= x:
			st += '1'
		elif full == x - 1 and part >= y:
			st += '1'
		else:
			st += '0'
	print(st)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	e = ''
	for _ in range(n):
		s = input()
		if s.count('F') >= x:
			e = e + '1'
		elif s.count('F') == x - 1 and s.count('P') >= y:
			e = e + '1'
		else:
			e = e + '0'
	print(e)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	st = ''
	for i in range(n):
		prob = input()
		u = 0
		p = 0
		f = 0
		for i in prob:
			if i == 'F' or i == 'f':
				f += 1
			elif i == 'U' or i == 'u':
				u += 1
			elif i == 'P' or i == 'p':
				p += 1
		if f >= x:
			st += '1'
		elif f == x - 1 and p >= y:
			st += '1'
		else:
			st += '0'
	print(st)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	ans = ''
	for i in range(n):
		M = input()
		F = M.count('F')
		P = M.count('P')
		if F >= x or (F == x - 1 and P >= y):
			ans = ans + '1'
		else:
			ans = ans + '0'
	print(ans)


t = int(input())
while t > 0:
	(a, b) = map(int, input().split())
	(m, n) = map(int, input().split())
	q = ''
	while a:
		s = input()
		p = s.count('P')
		f = s.count('F')
		u = s.count('U')
		if f >= m or (m - 1 == f and p >= n):
			q = q + '1'
		else:
			q = q + '0'
		a = a - 1
	print(q)
	t = t - 1


t = int(input())
while t != 0:
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	d = ''
	while n != 0:
		k = input()
		p = 0
		f = 0
		for j in k:
			if j == 'P':
				p += 1
			elif j == 'F':
				f += 1
		if f >= x or (p >= y and f >= x - 1):
			d += '1'
		else:
			d += '0'
		n -= 1
	print(d)
	t -= 1


t = int(input())
while t:
	(a, b) = map(int, input().split())
	(f, p) = map(int, input().split())
	ans = ''
	while a:
		s = input()
		x = s.count('F')
		y = s.count('P')
		if x >= f or (x == f - 1 and y >= p):
			ans += '1'
		else:
			ans += '0'
		a -= 1
	print(ans)
	t -= 1


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	c = ''
	for j in range(n):
		s = input()
		f = s.count('F')
		p = s.count('P')
		if f >= x:
			c += '1'
		elif f == x - 1 and p >= y:
			c += '1'
		else:
			c += '0'
	print(c)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	s = []
	for i in range(n):
		s.append(input())
	ans = []
	for j in s:
		if j.count('F') >= x or (j.count('F') == x - 1 and j.count('P') >= y):
			ans.append('1')
		else:
			ans.append('0')
	print(''.join(ans))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	c = ''
	for j in range(n):
		s = list(input())
		if s.count('F') >= x or (s.count('F') == x - 1 and s.count('P') >= y):
			c += '1'
		else:
			c += '0'
	print(c)


t = int(input())
for ni in range(t):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	l = ''
	for nj in range(n):
		s = input()
		nf = s.count('F')
		np = s.count('P')
		if nf >= x or (nf >= x - 1 and np >= y):
			l = l + '1'
		else:
			l = l + '0'
	print(l)


T = int(input())
for i in range(T):
	(M, N) = map(int, input().split())
	(X, Y) = map(int, input().split())
	for i in range(M):
		S = input()
		dic = {'F': 0, 'P': 0, 'U': 0}
		for i in S:
			dic[i] += 1
		if dic['F'] >= X:
			print(1, end='')
		elif dic['F'] == X - 1:
			if dic['P'] >= Y:
				print(1, end='')
			else:
				print(0, end='')
		else:
			print(0, end='')
	print()


for _ in range(int(input())):
	(candid, prob) = map(int, input().split())
	(x, y) = map(int, input().split())
	res = ''
	for i in range(candid):
		s = input()
		f = s.count('F')
		u = s.count('U')
		p = s.count('P')
		if f >= x or (f >= x - 1 and p >= y):
			res += '1'
		else:
			res += '0'
	print(res)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	data = [input() for i in range(0, n)]
	for i in data:
		solved = i.count('F')
		partiallySolved = i.count('P')
		if solved >= x:
			print(1, end='')
		elif solved == x - 1 and partiallySolved >= y:
			print(1, end='')
		else:
			print(0, end='')
	print()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	for k in range(n):
		s = input()
		c = s.count('F')
		c1 = x - 1
		c2 = s.count('P')
		if c >= x or (c == c1 and c2 >= y):
			print('1', end='')
		else:
			print('0', end='')
	print()


import numpy as np
T = int(input())
for i in range(T):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	result = []
	for i in range(n):
		attempt = input()
		f = attempt.count('F')
		p = attempt.count('P')
		u = attempt.count('U')
		if f >= x or (f == x - 1 and p >= y):
			result.append(1)
		else:
			result.append(0)
	print(*result, sep='')


t = int(input())
while t:
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	for i in range(n):
		s = input()
		p = s.count('F')
		q = s.count('P')
		if p >= x or (p == x - 1 and q >= y):
			print('1', end='')
		else:
			print('0', end='')
	print()
	t -= 1


for _ in range(int(input())):
	(N, M) = (int(a) for a in input().split())
	(X, Y) = (int(a) for a in input().split())
	result = ''
	for i in range(N):
		string = input()
		dict1 = {'F': 0, 'P': 0, 'U': 0}
		for i in string:
			if i in dict1:
				dict1[i] += 1
		if dict1['F'] >= X:
			result += '1'
		elif dict1['F'] >= X - 1 and dict1['P'] >= Y:
			result += '1'
		else:
			result += '0'
	print(result)


for mk in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	res = ''
	for i in range(n):
		a = input()
		if a.count('F') >= x or (a.count('F') == x - 1 and a.count('P') >= y):
			res += '1'
		else:
			res += '0'
	print(res)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	(x, y) = map(int, input().split())
	k = []
	for j in range(n):
		l = input()
		k.append(l)
	for key in k:
		full = part = un = 0
		for o in key:
			if o == 'F':
				full += 1
			elif o == 'U':
				un += 1
			else:
				part += 1
		if full == x - 1 and part >= y:
			print(1, end='')
		elif full >= x:
			print(1, end='')
		else:
			print(0, end='')
	print()