Swimming with Sharks

At one of the beaches in La Jolla, right by the pier, there are quite a few leopard sharks (they are only about 4 feet long, much smaller than most sharks). Some people find it thrilling to swim in the water together with these sharks. The contest organizers unanimously agree that this is not the greatest idea, and that if they ever found themselves in the water with a bunch of leopard sharks, their main goal would be to stay as far away from them as possible. Luckily, a (waterproof) computer can help with exactly that.

We model the water as a $w \times h$ two-dimensional grid of integer coordinates. At time $1$ you start at point $(1, 1)$. In each time step you may swim one square right, left, up, or down, or stay where you are, as long as you never leave the grid. You are given the positions of the sharks at various times, together with a time horizon $t$. You must plan your moves so as to stay as far from every shark as possible over the $t$ time steps.

More precisely, at each time step consider the distance from your position to the nearest shark that is present at that time step; let $d$ be the smallest such distance over all $t$ time steps (the closest you ever come to a shark). The distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is the Euclidean distance $d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$. Your goal is to choose a move plan that makes $d$ as large as possible while ending up back at position $(1, 1)$ at time $t$.

The first line contains a number $K \ge 1$, the number of data sets in the input. It is followed by $K$ data sets of the following form.

The first line of each data set contains four integers $w$, $h$, $t$, $s$. Here $1 \le w, h \le 10$ are the width and height of the water area, $1 \le t \le 100$ is the number of time steps you spend in the water, and $1 \le s \le 10000$ is the number of shark sightings.

This is followed by $s$ lines, each containing three integers $x_i$, $y_i$, $t_i$ with $1 \le x_i \le w$, $1 \le y_i \le h$, and $1 \le t_i \le t$. Such a line means that at time $t_i$ there is a shark at position $(x_i, y_i)$. The sightings are not sorted by any particular parameter.

For each data set, first output "Data Set x:" on a line by itself, where $x$ is the number of the data set (starting from $1$). Then output the closest you ever come to a shark in the best possible move plan, rounded to two decimals. (An output of $0.00$ means you cannot avoid occupying the same square as a shark at some time.)