Square Maze

Sajib is a criminal. Respected judge has sentenced him to prison for 10 years! He is now spending his lazy time in prison.

You are also trapped inside the prison with Sajib. Bored Sajib started playing with a rectangular grid of dimension $N * M$ where each element can be either an integer between 0 or 1. Sajib wants to find out the maximal area of a square consisting of only 1's from the rectangular grid. But there is a catch!

There are some special cells in the grid. Sajib knows there are exactly $K$ of them in the rectangular grid. He knows their positions as well. One can toggle the value of such cells from 0 to 1 or from 1 to 0 if they want, as many times as they wish! The cost of toggling $i_{th}$ special cell is given by $C_i$.

As Sajib is not a programmer (and you are), can you help him find out the maximal area of a square consisting of only 1's with minimum cost of toggling?

Input

The first line of the input contains an integer $T$ ($1 ≤ T ≤ 7$), number of test cases.

The second line of each input contains three integers $N$, $M$ ($1 ≤ N,M,C ≤ 1000$), and $K$ ($0 ≤ K ≤ min(N \times M, 10^4)$) denoting the number of rows, columns, and special cells respectively.

In the next $N$ lines, there will be $M$ space-separated integers.

After that, there will be $K$ lines for each test case. In each line, there will be three integers denoting the position (row and column) of the special cells and the $C_i$ ($1 ≤ C_i ≤ 1000$) cost of toggling the cell. All the indices will be 0-based.

Output

Print the desired maximal area and the minimum cost (space-separated) in a single line for each test case.

Sample

Input	Output
1 3 3 0 0 1 0 0 1 1 1 1 1	4 0

Large data set. Use faster I/O.

If there are multiple maximal squares satisfying all the conditions, you need to choose the one with minimum cost.