The Deer Hunter

P-22 eats deer, rabbits, and other animals in Griffith Park. He rarely attacks pets, though he is a prime suspect in the 2016 death of an elderly koala at the Los Angeles Zoo. Deer are very alert. You have to sneak up on them carefully, and if they hear or smell you before you pounce, you must run faster to catch them before they reach safety.

The hunting area is a rectangle. While sneaking, P-22 can move horizontally or vertically, but not diagonally. You are given the starting positions of P-22 and a grazing deer. Both start at the center of their squares. Each square is either silent or noisy. While P-22 stays on silent squares, the deer does not notice him. When he steps onto a noisy square, the deer starts running.

Precisely: while sneaking, each step starts and ends with P-22 at the center of a square. He makes noise when his center is at the center of a noisy square, not when he merely touches its edge.

When the deer starts running, it runs in a straight line directly away from P-22 at speed $v_D$. The line ignores the grid of the map. At that moment P-22 starts running at speed $v_P$ and follows the deer in a straight line. If he catches the deer before it reaches the edge of the area, he has a meal. Otherwise he goes hungry. The deer reaches the edge when its center touches the outer boundary of the area.

Running is much harder work than sneaking, so P-22 wants to run as briefly as possible. Find the shortest running time that P-22 can guarantee while still catching the deer.

The first line contains $1 \le K \le 100$, the number of data sets. Each data set starts with a line containing two integers $1 \le X, Y \le 1000$ and two real numbers $v_P, v_D > 0$. $X$ and $Y$ are the width and height of the hunting area, and $v_P$ and $v_D$ are the running speeds of P-22 and the deer.

Then $Y$ lines follow, each with $X$ characters. Character $x$ of line $y$ describes the square in column $x$ of row $y$:

• . is silent terrain.
• # is noisy terrain.
• P is P-22's starting square.
• D is the deer's starting square.

Both starting squares are silent. Each data set contains exactly one P and exactly one D.

For each data set, print Data Set x: on its own line, where $x$ is the data set number. On the next line, print the minimum running time of a successful hunt, rounded to two decimals. If P-22 cannot catch the deer, print -1 instead. Remember that P-22 and the deer are located at the centers of their squares, and the escape point is the outer edge of the area. Print a blank line after each data set.