PROBLEM LINK:
Author: Diwakar Bhardwaj
Tester: Suraj Prakash
Editorialist: Shubham Kabra
DIFFICULTY:
EASY
PREREQUISITES:
Dynamic Programming
PROBLEM:
Given a L*R matrix of character M and F, we have to find that whether K*K sub square matrix of M or F lies in the L*R matrix or not.
QUICK EXPLANATION:
Basically we have to find the maximum sub square matrix of M and F inside the given L*R matrix in order answer the further queries in linear time. Now, how can we find the maximum sub square matrix of M and F. Well, It is a standard problem of dynamic programming  Maximum sub square matrix in a given matrix.
EXPLANATION:
Let’s find the maximum sub square matrix all consist of ‘M’ in the given matrix then we can similarly find sub square matrix all consist of ‘F’.
Algorithm:
Let the given matrix of M and F is be S[][]. The idea of the algorithm is to construct an auxiliary size matrix A[][] in which each entry A[i][j] represents size of the square submatrix with all M's including S[i][j] where S[i][j] is the rightmost and bottommost entry in submatrix.

Construct a sum matrix A[L][R] for the given S[L][R].
a. Create first row and first column of A[][] as, if it is M in S[][], there will be 1 in A[][] otherwise 0.
b. For other entries, use following expressions to construct A[][]
If S[i][j] is 'M' then A[i][j] = min(A[i][j1], A[i1][j], A[i1][j1]) + 1 Else /*If S[i][j] is 'F'*/ A[i][j] = 0

Find the maximum entry in A[L][R], that will be the maximum sub square matrix all consist of M.

Store the maximum value in a integer variable max_m.
Now, using same algorithm we can find maximum sub square matrix all consist of F only by replacing M by F and viceversa and store it in another integer variable max_f.
For, the queries that will be asked further, we can directly print “yes” and “no” by checking the character and if K is greater than max_m or max_f (according to asked query for M or F) print “no” otherwise “yes”.
OPTIMAL COMPLEXITY:
\mathcal{O}(L*R + Q) where K is the number of levels.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.