Orienteering is a sport that combines intelligence and physical strength. In this activity, participants need to travel from a starting point to a designated destination in the shortest possible time.

Niuniu loves this sport, but he does not know how to reach the destination faster. He heard that you, who are participating in the training camp, are highly intelligent, so he handed you the orienteering map and hopes you can help him solve some problems.

The map Niuniu gave you describes a flat area. The map clearly marks the coordinates of the starting point and the destination, as well as several non-overlapping circular regions, each representing a circular body of water. For Niuniu, who cannot swim, entering the water is impossible. Therefore, Niuniu's route cannot pass through any water area. Niuniu wants to know the minimum possible length of such a route.

Input

The first line contains four real numbers $S_x, S_y, T_x, T_y$, representing the $x, y$ coordinates of the starting point and the $x, y$ coordinates of the destination, respectively.

The second line contains an integer $n$, representing the number of water areas.

The next $n$ lines each contain three integers $x_i, y_i, r_i$, representing the $x, y$ coordinates of the center and the radius of a water area.

It is guaranteed that the starting point and the destination are not inside or on the boundary of any water area, and the starting point and the destination do not coincide.

Output

Output a single line containing a real number, rounded to exactly 1 decimal place, representing the answer. Your output must be exactly the same as the standard output to be considered correct.

The test data guarantees that the absolute difference between the rounded answer and the accurate answer is no more than $4 \times 10^{-2}$.

(If you do not know what floating-point error is, this can be understood as: for most algorithms, you can use floating-point types normally without special handling.)

Examples

Input 1

2 1 20 11
2
5 5 4
16 9 4

Output 1

23.0

Note

The map is shown in the figure below, where the drawn path is the shortest path sought.

Input 2

See the provided file.

Output 2

See the provided file.

Constraints

For all data, $0 \le n \le 500, -1000 \le x_i, y_i, r_i, S_x, S_y, T_x, T_y \le 1000$.