Codeforces Global Round 9 |
---|
Finished |
A cubic lattice L in 3-dimensional euclidean space is a set of points defined in the following way: L={u⋅→r1+v⋅→r2+w⋅→r3}u,v,w∈Z Where →r1,→r2,→r3∈Z3 are some integer vectors such that:
You have to find a cubic lattice L such that A⊂L and r is the maximum possible.
First line contains single integer n (1≤n≤104) — the number of points in A.
The i-th of the following n lines contains integers xi, yi, zi (0<x2i+y2i+z2i≤1016) — coordinates of the i-th point.
It is guaranteed that gcd(g1,g2,…,gn)=1 where gi=gcd(xi,yi,zi).
In first line output a single integer r2, the square of maximum possible r.
In following 3 lines output coordinates of vectors →r1, →r2 and →r3 respectively.
If there are multiple possible answers, output any.
2 1 2 3 1 2 1
1 1 0 0 0 1 0 0 0 1
1 1 2 2
9 2 -2 1 1 2 2 -2 -1 2
1 2 5 5
9 -1 2 2 2 -1 2 2 2 -1
Name |
---|