There is a grid of r rows and c columns. The rows are numbered from 1 to r and the columns are numbered from 1 to c. The upper left cell is in row 1 and column 1. The lower right cell is in row r and column c. A cell (p, q) denotes the cell in row p and column q in the grid. A subgrid (r1, c1, r2, c2) is a part of the grid that contains all the cells from rows r1 to r2 and columns c1 to c2 (inclusive). In one unit of time you can move one marble from the cell (p, q) to any of the following 4 cells: cell(p − 1, q), cell(p + 1, q), cell(p, q − 1), cell(p, q + 1). You will be given the information of a grid. Then you will be given some sub- grids. For each subgrid your task is to calculate the minimum amount of time needed to move all the mar- bles to any of the cells in that sub grid. Input Figure 1: The figure above corresponds to the first sample input. The dashed rectangle shows the subgrid (1, 1, 2, 2). If we move all the marbles of this subgrid to cell (2, 2) the total cost will be (1∗2+2∗1+5∗1+6∗0) = 9. And this is the minimum possible cost, because the cost of moving all the marbles to (1, 1), (1, 2) and (2, 1) is 19, 17 and 11 respectively. This example corresponds to the second query of first sample input. First line of the input contains an integer T (T ≤ 3) the number of test cases. Each of the test cases begins with three integers r, c (1 ≤ r,c ≤ 500) and q (0 ≤ q ≤ 10000) in one line. Here r is the number of rows, c is the number of columns and q is the number of queries. Each of the next r lines contains c integers. The jth integer in the ith line contains the number of marbles in the cell(i,j). All these numbers are non- negative and less than 1001. Each of the next q lines contains 4 integers: r1, c1, r2, c2. These 4 integers denote the sub grid (r1, c1, r2, c2). You can obviously assume that (1 ≤ r1, r2 ≤ r and1≤c1,c2 ≤c) Output For each test case you have to produce q + 1 lines of output. The description of output for each test case is given below: First line of each test case contains the serial of that test case. Each of the next q line contains output for one query of that test case. Output for each query contains two integers separated by a single space. The first integer denotes the serial of the query and the second integer denotes the minimum time required to move the marbles within the query subgrid to one of the cells within the subgrid. Print a blank line after each test case.
2/2 Sample Input 2 343 1234 5678 9 10 11 12 1134 1122 1133 333 213 461 11 2 3 1133 1123 2133 Sample Output Test Case 1: 1 118 29 3 66 Test Case 2: 1 45 2 16 3 27