You are given a 2D character array denoting forest of length N and breadth M . In the matrix, '.' denotes barren land and ' * ' denotes tree.
You are given Q questions. In each question, you are given integer K and you have to determine the number of unique squares of side less than or equal to K which contain only trees.
Input
First line : N and M (N denoting number of rows and M denoting number of columns).
Each of the next N lines contains string of M length containing '.' and '*' .
Next line consists of an integer Q, denoting number of questions.
Each of the next Q lines contains a single integer K.
Input Constraints
\(1 \le N, M \le 1000\)
\(1 \le Q \le 10^5\)
\(0 \le K \le 10^3\)
Output
For each question, print the number of unique squares of side less than or equal to K which contain only trees. Answer for each question should come in a new line.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial