Processing math: 100%

I. Cubic Lattice
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A cubic lattice L in 3-dimensional euclidean space is a set of points defined in the following way: L={ur1+vr2+wr3}u,v,wZ Where r1,r2,r3Z3 are some integer vectors such that:

  • r1, r2 and r3 are pairwise orthogonal: r1r2=r1r3=r2r3=0 Where ab is a dot product of vectors a and b.
  • r1, r2 and r3 all have the same length: |r1|=|r2|=|r3|=r
You're given a set A={a1,a2,,an} of integer points, i-th point has coordinates ai=(xi;yi;zi). Let gi=gcd(xi,yi,zi). It is guaranteed that gcd(g1,g2,,gn)=1.

You have to find a cubic lattice L such that AL and r is the maximum possible.

Input

First line contains single integer n (1n104) — the number of points in A.

The i-th of the following n lines contains integers xi, yi, zi (0<x2i+y2i+z2i1016) — coordinates of the i-th point.

It is guaranteed that gcd(g1,g2,,gn)=1 where gi=gcd(xi,yi,zi).

Output

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.

Examples
Input
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