
ZOJ Problem Set  3477
Akasim Matrix is the most powerful grid computing platform developed by Academy City. Each node is identified by its serial number  a 2tuple (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 (x_{i}, y_{i}) at day d_{i}. 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 antivirus as well as many other principles of science. They can clear all virus as long as they successfully build an antivirus 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 antivirus program at. InputThere 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 ≤ 2^{20}, 1 ≤ m ≤ 2^{19} and 1 ≤ v ≤ 218. Then v lines, the ith line contains three integers 1 ≤ x_{i} ≤ n, 1 ≤ y_{i} ≤ m and 0 ≤ d_{i} < 1,000,000,000. Each test case ends with a blank line. OutputFor each test case, output "d (x, y)". In case that more than one nodes are infected at the dth day, you should first minimize the x, then minimize the y. Sample Input3 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 Output3 (1, 1) 5 (1, 1) 3 (2, 2) Author: WU, Zejun Contest: The 11th Zhejiang University Programming Contest 