Lowest Latency

문제

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 astonomy class, you know that the universe is best modelled as a large cube measuring ${10}^{9}10^9$ lightyears in each dimension. There are exactly ${10}^{5}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 $00$ to ${10}^{9}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.

입력

The input consists of:

• One line with an integer $nn$, the number of planets.
• $nn$ lines, each with three integers $xx$, $yy$, and $zz$ (), the coordinates of one of the planets.

Your submissions will be run on exactly $100100$ test cases, all of which will have $n={10}^{5}n\; =\; 10^5$. The samples are smaller and for illustration only.

Each of your submissions will be run on new random test cases.

출력

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}10^\{-6\}$.