405245: GYM101856 I Important matches

In the qualification rounds of the World Cup, there were two disjoint sets of teams S₁ = [1, ..., N] and S₂ = [1, ..., M]. Given a matrix X that decides the importance of the match between team against team by the value X_i, j. S₁ represents the rows of the matrix X, and S₂ represents the columns of the matrix X. We would like to answer Q queries, where each decides the importance of all the matches played by all the teams from the subgroup [A, ..., C] from S₁ against all teams from the subgroup [B, ..., D] from S₂, such that 1 ≤ A ≤ C ≤ N, 1 ≤ B ≤ D ≤ M. The importance of a set of matches between two subgroups is determined by the median importance of all the matches between the teams from the first subgroup against all the teams from the second group, namely the median of the submatrix X_{A... C, B... D}.

The first line of the input contains a single integer 1 ≤ T ≤ 100 the number of test cases. Each test case begins with a line containing 3 spaces separated integers N, M, Q. The importance matrix X is given by the next N lines each containing M space separated integers. The remaining Q lines, each contains 4 space separated integers A, B, C, D of the query; where 1 ≤ N, M ≤ 200, 1 ≤ Q ≤ 10000, and for the given importance matrix X, 1 ≤ X_i, j ≤ 2000 for all i, j.

For each test case output a line displaying the case number, followed by Q lines each containing a single integer, the importance of the matches of the corresponding query.

1
3 4 2
1 2 3 1
2 1 1 4
7 8 9 3
1 1 1 1
1 2 3 4

Case 1:
1
3

• The median of a set of numbers is the middle element in the sorted list of the given set. If the set has two middle elements, then we choose the second one. For example the median of {2, 1, 3} is 2 and the median of {4, 2, 3, 1} is 3.
• The second query asks for the median of the submatrix that is excluding the first column. This submatrix contains the elements {2, 3, 1, 1, 1, 4, 8, 9, 3}, which has the sorted form {1, 1, 1, 2, 3, 3, 4, 8, 9}, therefore the median is 3.