405085: GYM101778 F Median and Queries

You are given a grid consisting of n rows each of which is dived into m columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to m from left to right. Each cell is identified by a pair (x, y), which means that the cell is located in the row x and column y. All cells in the grid contain positive integers.

Also, q queries are given, such that each query consists of four integers a, b, c and d. For each query, the task is to find the median of a sub-matrix (a, b) (c, d) in the given grid.

A sub-matrix (a, b) (c, d) is defined as all cells whose satisfying the following conditions: (a ≤ x ≤ c) and (b ≤ y ≤ d). The following picture describes a grid of 4 rows and 5 columns. The shaded part shows the sub-matrix (2, 2) (3, 4).

Sarah needs your help to find the answer to each query. Can you help her?

The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.

The first line of each test case contains three integers n, m, and q (1 ≤ n, m ≤ 100) (1 ≤ q ≤ 10⁵), in which n is the number of rows in the grid, m is the number of columns in the grid, and q is the number of queries.

Then n lines follow, each line contains m integers, giving the grid. All values in the grid are between 1 and 500 (inclusive).

Then q lines follow, each line contains four integers a, b, c, and d (1 ≤ a ≤ c ≤ n) (1 ≤ b ≤ d ≤ m), giving the queries.

The sum of n × m overall test cases does not exceed 3 × 10⁵, and the sum of q overall test cases does not exceed 10⁶.

For each query, print a single line containing the median value.

1
4 4 3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 1 2 2
1 2 3 3
1 3 4 3

2
6
7

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 first one. For example, the median of {2, 1, 3} is 2 and the median of {4, 2, 3, 1} is 2.