B. Cowpproximation
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are cows in a 2 by 2 kilometer field. The cows want to have a group meeting, and all of them must attend! It is up to you to plan the meeting to take place as soon as possible.

To model this problem, we approximate each cow as a circle, and for our purposes, there are no collisions - cows can pass through each other freely.

The $$$i$$$-th cow is represented by its initial position $$$\left(x_{i}, y_{i}\right)$$$ and its radius $$$r_{i}$$$, all distances are measured in meters. You can tell each cow to travel in any direction from its initial position at a constant speed from 0 to 1 meter per second. The meeting takes place as soon as all cows occupy the same point in the plane, i.e., there exists a point contained within all circles representing the cows. Find the minimum time in seconds required for the cows to meet.

Input

The first input line contains a single integer $$$N$$$ $$$(1 \leq N \leq 10^{3})$$$, representing the number of cows. Each of the following $$$N$$$ lines contains three space separated integers $$$x_{i}, y_{i}, r_{i}$$$, describing a cow, where $$$-10^{3} \leq x_{i}, y_{i} \leq 10^{3}$$$ and $$$1 \leq r_{i} \leq 10^{3}$$$.

Output

Output the minimum time $$$T$$$ in seconds after which all the cows meet. Your answer will be considered correct if it has an absolute or relative error at most $$$10^{-5}$$$. Formally, let $$$T_{O P T}$$$ be the optimal value. Then your answer is considered correct if either $$$\left|T-T_{O P T}\right| \leq 10^{-5}$$$ or $$$\left|\frac{T-T_{O P T}}{\max \left\{1, T_{O P T}\right\}}\right| \leq 10^{-5}$$$ holds.

Examples
Input
2
-10 3 2
10 3 4
Output
7.0000000
Input
3
-4 -4 1
6 0 3
0 8 5
Output
3.7039181
Note
Figure 1: Visualization of sample input 1. The empty dot represents the meeting location. Figure 2: Visualization of sample input 2. The empty dot represents the meeting location.