578. Bomb the Bridge

The Air Force has a special team devoted to destroying bridges. This team is composed of several planes which over the targeted bridge one after another. Each of these planes carries one bomb, which the pilot drops at a given location in the bridge. The aim of the team is to split the bridge in two, so that no one can cross it.

Unfortunately, bombs are not completely accurate. As a result, even though missions are planned in advance, the exact location where the bombs actually fall may be different than planned. Still, the Air Force keeps his original plan untouched except for the last plane, which may have to act differently.

Each bomb that is dropped on the bridge leaves a hole that, viewed from above, has the shape of a circle, its radius depending on the power of the bomb. A bomb of size s leaves a hole of radius s. Your task is to determine the plan for the last plane, that is, the minimum bomb size and the position where the last plane should drop the bomb so that, if everything goes well, the bridge is split in two.

The first line contains a positive integer `n`, representing the number of instances of the problem contained on the input file.

Each instance is represented by three positive integers `w`, `l` and `b`, which denote the width and length of the bridge and the amount of bombs dropped on the bridge. Then come `b` lines, each containing integers `x`, `y` and `r` (`x,\ y\ ≥\ 0`, `r\ >\ 0`) which denote the coordinates of the center and the radius of the holes left by the b bombs. Coordinate (0,0) is the lower-left corner of the bridge (viewed from above), assuming that the bridge has width parallel to the `x` axis and length parallel to the `y` axis.

Your program must produce one output line for each instance. This line contains an integer representing the minimum bomb size you need to split the bridge in two, or the words Bridge already split if the bridge is already split by the bombs that have been dropped. The bridge is considered to be split if the two ends of the bridge are disconnected (except perhaps for a finite number of points). Remember that a bomb of size `s` leaves a hole of radius `s`.

3
100 1000 2
15 100 20
90 100 30
100 1000 1
50 100 40
100 1000 2
25 500 25
75 500 25

13 
50 
Bridge already split