Handbags

Handbags are a popular souvenir everywhere in the city of Manhattanila, because the city makes them itself.

Manhattanila has $(a+1)(b+1)$ villages, locally called barangays, laid out neatly in an $(a+1) \times (b+1)$ rectangular lattice. A village is named by two integers $(x, y)$ with $0 \le x \le a$ and $0 \le y \le b$, its row number and its column number, both counted from 0.

Exactly $s$ of the villages make handbags. Call these the source villages. Every other village buys its handbags from a neighboring village. Two villages are neighbors when they share a boundary, so a village has up to four neighbors, one in each cardinal direction. A neighbor need not be a source village, so it may buy its own supply from another neighbor, and so on.

A source village makes handbags at a fixed price of its own. A village that buys from a neighbor selling at $p$ pesos sells at $p+1$ pesos. Every village pays as little as it can: it buys from the neighbor that sells cheapest, and a source village sells at its own price or at its cheapest neighbor's price plus 1, whichever is smaller. These rules give every village exactly one price.

A tourist comes to Manhattanila for souvenirs (pasalubong). To impress her friends she plans to say that she bought her handbags in the village where they cost the most, while she quietly buys them in the village where they cost the least. Answer her question: what is the highest price of a handbag in the city, and how many villages sell at that price?

The first line contains $T$, the number of test cases.

The first line of each test case contains three integers $a$, $b$ and $s$, where $s$ is the number of source villages. Each of the next $s$ lines contains three integers $x$, $y$ and $p$, meaning that village $(x, y)$ is a source village and sells its handbags at $p$ pesos. No pair $(x, y)$ appears twice in one test case.

Constraints

• $1 \le T \le 50000$
• $0 \le a, b \le 10^6$
• $0 \le x \le a$
• $0 \le y \le b$
• $1 \le s \le 30$
• $1 \le p \le 10^9$
• The sum of $s$ over all test cases is at most $50000$.

For each test case, print one line with two integers separated by a space:

• the highest price of a handbag in the city, and
• the number of villages that sell at that price.