Home Notification Clarification Problems Ranklist Status Statistics Print

Seashells

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3    Accepted Submission(s): 0


Problem Description
Bob lived on an island which has many kinds of beautiful seashells. We can regard this island as a rectangular grid that is n rows by m columns. Assume that the coordinates of the j-th column of the i-th row is (i, j). The coordinates of Bob's house is (x, y). There is at most one kind of seashells in each cell. Bob likes collecting seashells very much. However, he can only go the place of coordinates (x0, y0) with |x0-x|+|y0-y|<=A and max(|x0-x|, |y0-y|) <= B. How many kinds of seashells can Bob get at most?
 

Input
The first line contains the number T of test cases (T<=5). The first line of each test cases contains four integer numbers n, m, x and y (1<=x<=n<=1000, 1<=y<=m<=1000). The following n lines each containing m integers indicating the type of the seashells. The seashells are different if and only if the corresponding integers are different. The next line contains a single integer q (q <= 105) indicating the number of queries. Each of the following q lines contains two integers A and B(0<=A,B<1000).
 

Output
For each queries, output a single line contains a single integer indicating the number of seashells Bob can get.
 

Sample Input
1 4 4 1 2 1 2 3 4 3 2 1 4 5 3 2 654321 2 3 4 6 4 2 1 1 0 3 2 999 999
 

Sample Output
3 1 5 7
 

Author
hanshuai@WHU
 

Statistic | Submit | Clarifications | Back