Apple Orchard

All submissions for this problem are available.
Problem Statement
Jason and his dad own an apple orchard of size N x M. And every fall he would help his father pick apples for the production of cider. But the cider press can take only K kilograms a day due to its small size. Every day he would pick apples only in a special subrectangle which has size S x T where S<=X and T<=Y, for some fixed X and Y. He has Q queries, each query contains X, Y. For each query, he wanted to know how many special subrectangles contain at least K kilograms of apples..
Input
The first line of the input contains integers N, M and K(1<=N, M<=300, 1<=K<=N*M).
The next N lines contain M characters (either 'A' or '.'). 'A' means there is 1 kg of apples in that cell, while '.' means there are no apples in that cell.
The next line contains an integer Q (1<=Q<=100 000).
The next Q lines contain integers X and Y (1<=X<=N , 1<=Y<=M).
Output
The output contains Q lines, each line contains the number of special subrectangles which satisfy the requirement. (The amount of apples is at least K inside the special subrectangle)
Example
Input: 5 5 4 A.A.. ..A.. A...A AAAA. AA..A 2 1 1 2 3 Output: 0 4
Note : The reference for this problem has been taken from : Codechef
Author:  himanshuk123 
Tags  himanshuk123 
Date Added:  13102013 
Time Limit:  0.169811 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 