410428: GYM104020 L Lowest Latency

L. Lowest Latencytime limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

It is the year 2222. The whole universe has been explored, and settlements have been built on every single planet. You live in one of these settlements. While life is comfortable on almost all aspects, there is one dire problem: the latency on the internet connection with other planets is way too high.

Luckily, you have thought of a solution to solve this problem: you just need to put Bonded, Astronomically Paired Cables between all planets, and internet will be super fast! However, as you start developing this idea, you discover that constructing a cable between two planets is more difficult than expected. For this reason, you would like the first prototype of your cable to be between two planets which are as close as possible to each other.

From your astronomy class, you know that the universe is best modelled as a large cube measuring $$$10^9$$$ lightyears in each dimension. There are exactly $$$10^5$$$ stationary planets, which are distributed completely randomly through the universe (more precisely: all the coordinates of the planets are independent uniformly random integers ranging from $$$0$$$ to $$$10^9$$$).

Given the random positions of the planets in the universe, your goal is to find the minimal Euclidean distance between any two planets.

Input

The input consists of:

• One line with an integer $$$n$$$, the number of planets.
• $$$n$$$ lines, each with three integers $$$x$$$, $$$y$$$, and $$$z$$$ ($$$0 \leq x, y, z < 10^9$$$), the coordinates of one of the planets.

Your submissions will be run on exactly $$$100$$$ test cases, all of which will have $$$n = 10^5$$$. The samples are smaller and for illustration only. Each of your submissions will be run on new random test cases.Output

Output the minimal Euclidean distance between any two of the planets.

Your answer should have an absolute or relative error of at most $$$10^{-6}$$$.

ExamplesInput

5
10 5 1
8 2 0
4 7 5
1 0 9
0 10 7

Output

3.7416573867739413

Input

3
790726336 656087587 188785845
976472310 22830435 160538063
211966015 87530388 542618498

Output

660540781.9387681