I. Cubic Latticetime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputA cubic lattice L in 3-dimensional euclidean space is a set of points defined in the following way: L=\{u \cdot \vec r_1 + v \cdot \vec r_2 + w \cdot \vec r_3\}_{u, v, w \in \mathbb Z} Where \vec r_1, \vec r_2, \vec r_3 \in \mathbb{Z}^3 are some integer vectors such that:   \vec r_1, \vec r_2 and \vec r_3 are pairwise orthogonal: \vec r_1 \cdot \vec r_2 = \vec r_1 \cdot \vec r_3 = \vec r_2 \cdot \vec r_3 = 0 Where \vec a \cdot \vec b is a dot product of vectors \vec a and \vec b.  \vec r_1, \vec r_2 and \vec r_3 all have the same length: |\vec r_1| = |\vec r_2| = |\vec r_3| = r  You're given a set A=\{\vec a_1, \vec a_2, \dots, \vec a_n\} of integer points, i-th point has coordinates a_i=(x_i;y_i;z_i). Let g_i=\gcd(x_i,y_i,z_i). It is guaranteed that \gcd(g_1,g_2,\dots,g_n)=1.You have to find a cubic lattice L such that A \subset L and r is the maximum possible.InputFirst line contains single integer n (1 \leq n \leq 10^4) — the number of points in A.The i-th of the following n lines contains integers x_i, y_i, z_i (0 < x_i^2 + y_i^2 + z_i^2 \leq 10^{16}) — coordinates of the i-th point.It is guaranteed that \gcd(g_1,g_2,\dots,g_n)=1 where g_i=\gcd(x_i,y_i,z_i).OutputIn first line output a single integer r^2, the square of maximum possible r.In following 3 lines output coordinates of vectors \vec r_1, \vec r_2 and \vec r_3 respectively.If there are multiple possible answers, output any.ExamplesInput
2
1 2 3
1 2 1
Output
1
1 0 0
0 1 0
0 0 1
Input
1
1 2 2
Output
9
2 -2 1
1 2 2
-2 -1 2
Input
1
2 5 5
Output
9
-1 2 2
2 -1 2
2 2 -1

2
1 2 3
1 2 1

1 1 0 0 0 1 0 0 0 1 
['geometry', 'math', 'matrices', 'number theory', '*3500']