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: interview

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
##    for i in xrange(row+1):
##        for j in xrange(col+1):
##            print dp[i][j],
##        print
 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')
 else:
  if male.get(int(query[0]),0)==0:
   print('no')
  else:
   print('yes')


def matrix(L,n,m,c):
 d={}
 dp=[[0]*(m+1)]*(n+1)
 for i in range(1,n+1):
  for j in range(1,m+1):
   if L[i-1][j-1]==c:
    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
   else:
    dp[i][j]=0
   d[dp[i][j]]=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')
 else:
  if 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')