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.
In the given sample , as we can see :-
Squares of side 1 containing only trees :- 12.
Squares of side 2 containing only trees :- 4.
Squares of side 2 containing only trees :- 1.
Thus answer for query 1 is 12.
Answer for query 2 i.e squares of side less than or equal to 2 are 12+4 = 16.
Answer for query 3 i.e squares of side less than or equal to 3 are 12+4+1=17.
