The Temple

A team of archaeologists is about to start excavating an ancient temple, and the first task is to light up the site. The temple is a wide, flat floor on which many tall cylindrical columns stand. The team puts one power source and several lamps on the floor and wants to connect every lamp to the power source with the shortest possible wire. Find the length of each wire.

To keep the model simple, assume the following:

• no two columns touch each other;
• a wire has no thickness, must lie flat on the floor, and may touch a column but may never pass through it;
• the power source and the lamps are treated as points and never touch a column.

Viewed from above, the columns are circles and the power source and lamps are points. For each lamp, write a program that computes the length of the shortest wire connecting it to the power source.

The first line contains the number of columns $n$ ($1 \le n \le 300$). Each of the next $n$ lines describes one column with three integers $x$, $y$, $r$ ($1 \le r \le 5000$, $r \le x, y \le 10000 - r$): the centre $(x, y)$ and the radius $r$ of the column. The next line contains the number of lamps $m$ ($1 \le m \le 200$). Each of the next $m$ lines contains the coordinates $x_i$, $y_i$ ($0 \le x_i, y_i \le 10000$) of one lamp. The last line contains the coordinates $x_a$, $y_a$ ($0 \le x_a, y_a \le 10000$) of the power source.

Print $m$ lines. On the $i$-th line, print the length of the shortest wire connecting the $i$-th lamp to the power source, rounded to exactly six digits after the decimal point (such as 9.278662).

The figure illustrates a layout of columns and wires.