Seashells

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 (x₀, y₀) with |x₀-x|+|y₀-y|<=A and max(|x₀-x|, |y₀-y|) <= B. How many kinds of seashells can Bob get at most?

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 <= 10⁵) indicating the number of queries. Each of the following q lines contains two integers A and B(0<=A,B<1000).

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

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

3
1
5
7

hanshuai@WHU

HDOJ Monthly Contest – 2010.02.06