Given a 2D 4-connected grid. Each cell contains a value and an identifier. Values can be propagated from one cell to another.
Propagation logic is: values of Cell (a, b) propagate to cell (c, d) if and only if (a, b) and (c, d) are neighbors and identifier of (c, d) is smallest among all the neighbors of (a, b).
Neighbors of cell (a, b) are: (a+1, b), (a, b+1), (a-1, b), (a, b-1) and (a, b) itself.
After propagation, values of (c, d) is increased by values of (a, b) and values of (a, b) becomes zero.
The problem is to find out the cell whose value is maximum after completing all propagation.
In case there are multiple solutions with maximum value, select the cell with the largest row number. If this ties again, select the cell with largest column number. Print the cell coordinates and the value in it after all of the propagation.
For each cell, there will be only one neighbor whose identifier is the smallest.
Input starts with an integer T (1 ≤ T ≤ 10) denoting the number of test cases. Each test case begins with two integer number N and M (1 ≤ N, M ≤ 500) denoting rows and columns of grid. Following N lines contains M space separated integers denoting identifier grid. Next, N lines contains M space separated integers denoting value of each cell. Grid values and identifiers will be at most 5000.
For each case of input, output a single line with 3 space separated integers. First two integers denote the grid cell and third one represent the maximum value formed after propagation. Coordinate of left upper cell is (0, 0) and coordinate of right bottom cell is (N-1, M-1).
| Input | Output |
|---|---|
1 2 2 1 2 3 4 1 2 3 4 | Case #1: 0 0 10 |