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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "def max_size(mat, ZERO=0):\n nrows, ncols = len(mat), (len(mat[0]) if mat else 0)\n if not (nrows and ncols): return 0 \n counts = [[0]*ncols for _ in range(nrows)]\n for i in reversed(range(nrows)):    \n  assert len(mat[i]) == ncols \n  for j in reversed(range(ncols)): \n   if mat[i][j] != ZERO:\n    counts[i][j] = (1 + min(\n     counts[i][j+1],  \n     counts[i+1][j],  \n     counts[i+1][j+1] \n     )) if i < (nrows - 1) and j < (ncols - 1) else 1 \n return max(c for rows in counts for c in rows)\n\nl,r,k=list(map(int,input().split()))\na,ans=[],['no','yes']\nfor _ in range(0,l):\n q=input().replace('M','1').replace('F','0')\n a.append(list(map(int,list(q))))\nf = max_size(a,1)\nm = max_size(a,0)\nfor _ in range(0,k):\n n,q = input().split()\n if q=='M':\n  print(ans[int(n)<=m])\n else:\n  print(ans[int(n)<=f])"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13541