The auditorium of Stanford University is made up of L*R matrix (assume each coordinate has a chair). On the occasion of an event Chef was called as a chief guest. The auditorium was filled with males (M) and females (F), occupying one chair each. Our Chef is very curious guy, so he asks the gatekeeper some queries. The queries were as follows: Is there any K*K sub-matrix in the auditorium which contains all Males or Females.

-----Input-----
- The first line contains three space-separated integers L, R  and Q describing the dimension of the auditorium and the number of questions Chef will ask.
- Each of next L lines contains R characters (M or F).
- Next Q lines contains K and a character (M or F).

-----Output-----
- For each query output "yes" (without quotes) if there exist any K*K sub-matrix in the auditorium which contains all Males (if he asks about Male) or Females (if he asks about Female), otherwise output "no" (without quotes).

-----Constraints and Subtasks-----
- 1 <= L, R, K <= 1000
- 1 <= Q <= 1e6
Subtask 1: 30 points
- 1 <= L, R, Q <= 200
Subtask 2: 70 points
- Original Contraints

-----Example-----
Input:
4 3 3
MMF
MMM
FFM
FFM
2 F
3 M
1 M

Output:
yes
no
yes

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def matrix(L, row, col, c):
	d = {}
	dp = []
	for i in range(row + 1):
		temp = []
		for i in range(col + 1):
			temp.append([])
		dp.append(temp)
	for i in range(row + 1):
		dp[i][0] = 0
	for i in range(col + 1):
		dp[0][i] = 0
	for i in range(1, row + 1):
		for j in range(1, col + 1):
			if L[i - 1][j - 1] == c:
				dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
			else:
				dp[i][j] = 0
			d[dp[i][j]] = d.get(dp[i][j], 0) + 1
	return d
from sys import stdin
(n, m, q) = list(map(int, stdin.readline().split()))
L = []
for i in range(n):
	L.append(stdin.readline().strip())
male = matrix(L, n, m, 'M')
female = matrix(L, n, m, 'F')
for i in range(q):
	query = stdin.readline().split()
	if query[1] == 'F':
		if female.get(int(query[0]), 0) == 0:
			print('no')
		else:
			print('yes')
	elif male.get(int(query[0]), 0) == 0:
		print('no')
	else:
		print('yes')


def max_size(mat, ZERO=0):
	(nrows, ncols) = (len(mat), len(mat[0]) if mat else 0)
	if not (nrows and ncols):
		return 0
	counts = [[0] * ncols for _ in range(nrows)]
	for i in reversed(range(nrows)):
		assert len(mat[i]) == ncols
		for j in reversed(range(ncols)):
			if mat[i][j] != ZERO:
				counts[i][j] = 1 + min(counts[i][j + 1], counts[i + 1][j], counts[i + 1][j + 1]) if i < nrows - 1 and j < ncols - 1 else 1
	return max((c for rows in counts for c in rows))
(l, r, k) = list(map(int, input().split()))
(a, ans) = ([], ['no', 'yes'])
for _ in range(0, l):
	q = input().replace('M', '1').replace('F', '0')
	a.append(list(map(int, list(q))))
f = max_size(a, 1)
m = max_size(a, 0)
for _ in range(0, k):
	(n, q) = input().split()
	if q == 'M':
		print(ans[int(n) <= m])
	else:
		print(ans[int(n) <= f])


def chk():
	for r in range(i + 1, i + k):
		if m[r][ix:ix + k] != ss:
			return False
	return True
(l, r, q) = list(map(int, input().split()))
m = [input().replace(' ', '') for _ in range(l)]
for _ in range(q):
	(k, s) = input().split()
	k = int(k)
	ss = k * s
	ans = 'no'
	for i in range(l - k + 1):
		st = 0
		while ss in m[i][st:]:
			ix = m[i].index(ss, st)
			if chk():
				ans = 'yes'
				break
			st = ix + 1
		if ans == 'yes':
			break
	print(ans)


read = lambda : list(map(int, input().split()))
read_s = lambda : list(map(str, input().split()))

def found(K, gender, L, R):
	ans = []
	for i in range(K):
		ans.append(gender * K)
	for i in range(L - K + 1):
		for j in range(R - K + 1):
			Query_list = []
			for qq in range(K):
				Query_list.append(grid[i + qq][j:j + K])
			if Query_list == ans:
				return True
	return False
(L, R, Q) = read()
grid = []
for i in range(L):
	grid.append(str(input()))
for i in range(Q):
	(K, gender) = input().split()
	(K, gender) = (int(K), str(gender))
	print('yes' if found(K, gender, L, R) else 'no')