C. Crop Circles
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

After a series of unfortunate events, dubious investments, and catastrophically failed marriages, Camila has decided to leave Earth for good. She does not have enough money to build a rocket, so her best hope is to be abducted by aliens. Camila asked an AI chatbot about it, and then she independently came to the conclusion that the best way to be abducted by aliens is by making a circle of crops.

The good news is that among Camila's poor investments there is a very large farm, which can be represented as the 2D plane. There are $$$N$$$ sprinklers located on the farm, and each of them waters all plants within a radius that depends on its power. Camila's plan is to plant corn seeds in a perfect circle. Since the soil of the farm is very dry, the whole perimeter of Camila's circle must be watered by some sprinkler. Notice that Camila only needs to water the perimeter of the circle, while areas inside of it may remain dry.

To maximize her abduction chances, Camila's circle needs to be as large as possible. Since you are one of her few remaining friends, she asks for your help to determine what is the largest circle of corn she can plant on her farm, given the position and radius of each sprinkler.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 40$$$) indicating the number of sprinklers.

Each of the next $$$N$$$ lines describes a sprinkler with three integers $$$X$$$, $$$Y$$$ and $$$R$$$ ($$$-1000 \leq X, Y \leq 1000$$$ and $$$1 \le R \leq 1000$$$), indicating that the sprinkler has coordinates $$$(X,Y)$$$ and waters all plants within a radius of $$$R$$$, inclusive.

No two sprinklers have the same location.

Output

Output a single line with the maximum radius of a crop circle Camila can build. Notice that although the sprinklers have integer coordinates and radii, the coordinates and radius of the crop circle are not required to be integers. The output must have an absolute or relative error of at most {$$$10^{-6}$$$}.

Examples
Input
4
1 1 1
-1 1 1
-1 -1 1
1 -1 1
Output
1.0000000000
Input
1
3 1 415
Output
415.0000000000
Input
4
1 0 2
-1 0 2
0 1 2
0 -1 2
Output
2.5779354746
Note

Explanation for example 1

Camila can choose among five crop circles of radius $$$1$$$. Four of them are centered at the sprinklers, while the remaining one is centered at $$$(0,0)$$$.