## Problem G. Gathering ants ≡

• problems
 Author: A. Baranov Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

### Statement

Let us consider 3-dimensional area that is split by uniform rectangular grid. Some cells contain ants. Each second every ant can either stay put or move to the neighboring cell in any of the six directions: up, down, right, left, forward and backward.

Your program must, given coordinates of starting cell for each ant, find minimum possible number of seconds (starting from zero) until any two ants meet in the same cell.

### Input file format

Input file contains integer N followed by N triples of integer indices Xi, Yi, Zi — coordinates of starting cells for each ant.

### Output file format

Output file must contain a single integer — minimal number of seconds until two ants meet.

### Constraints

− 106 ≤ (Xi, Yi, Zi) ≤ 106, 2 ≤ N ≤ 5 ⋅ 104

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5
1 19 37
-9 5 10
4 3 6
9 8 7
17 20 5
6
2
5
6 49 58
-9 -1 3
2 8 9
-1 2 0
2 8 9
0

0.078s 0.011s 13