Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3477
Akasim Matrix

Time Limit: 7 Seconds      Memory Limit: 65536 KB

Akasim Matrix is the most powerful grid computing platform developed by Academy City. Each node is identified by its serial number -- a 2-tuple (x, y). The node with serial number (x, y) can communicate with its neighbors, namely (x - 1, y), (x + 1, y), (x, y - 1) and (x, y + 1), if exists. The Akasim Matrix is made up of n * m nodes whose serial numbers vary from (1, 1) to (n, m).

Recently, some magical girls attacked the Akasim Matrix. They injected an extremely infectious virus called soldier of love into the node (xi, yi) at day di. The virus spread very fast, every day, an infected node will make all its neighbors infected. The soldier of love will devastate the Akasim Matrix once it infects all nodes. Academy City has very advanced technologies in anti-virus as well as many other principles of science. They can clear all virus as long as they successfully build an anti-virus program at any node before it's infected. But this process does cost a long long time. So they want to know how many days they have at most and which node they should build the anti-virus program at.

Input

There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases.

Each test case starts with three integers 1 ≤ n ≤ 220, 1 ≤ m ≤ 219 and 1 ≤ v ≤ 218. Then v lines, the i-th line contains three integers 1 ≤ xin, 1 ≤ yim and 0 ≤ di < 1,000,000,000. Each test case ends with a blank line.

Output

For each test case, output "d (x, y)". In case that more than one nodes are infected at the d-th day, you should first minimize the x, then minimize the y.

Sample Input

3
3 3 1
2 2 1

3 3 1
3 3 1

3 3 4
1 1 1
1 3 1
3 1 1
3 3 1

Sample Output

3 (1, 1)
5 (1, 1)
3 (2, 2)

Author: WU, Zejun
Contest: The 11th Zhejiang University Programming Contest
Submit    Status