Problem: A cubic lattice L in 3-dimensional euclidean space is a set of points defined in the following way: $$$L=\\{u ⋅ \vec r_1 + v ⋅ \vec r_2 + w ⋅ \vec r_3\}_{u, v, w ∈ \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 ⋅ \vec r_2 = \vec r_1 ⋅ \vec r_3 = \vec r_2 ⋅ \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, ..., \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,...,g_n)=1.

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

Input

First line contains single integer n (1 ≤ n ≤ 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 ≤ 10^{16}) — coordinates of the i-th point.

It is guaranteed that \gcd(g_1,g_2,...,g_n)=1 where g_i=\gcd(x_i,y_i,z_i).

Output

In 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.

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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
std::mt19937 rnd(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
struct HurwitzQuat {
  long long s, x, y, z;
  HurwitzQuat(long long s = 0, long long x = 0, long long y = 0,
              long long z = 0)
      : s(s), x(x), y(y), z(z) {}
};
void printdiv2(long long v) {
  if (v < 0) printf("-"), v = -v;
  printf("%lld.%lld", v / 2, v % 2 * 5);
}
void print(const HurwitzQuat &a) {
  printf("(");
  printdiv2(a.s);
  printf(",");
  printdiv2(a.x);
  printf(",");
  printdiv2(a.y);
  printf(",");
  printdiv2(a.z);
  printf(")");
}
long long norm(const HurwitzQuat &a) {
  long long ret = a.s * a.s + a.x * a.x + a.y * a.y + a.z * a.z;
  assert(ret % 4 == 0);
  return ret / 4;
}
HurwitzQuat conj(const HurwitzQuat &a) {
  return HurwitzQuat(a.s, -a.x, -a.y, -a.z);
}
HurwitzQuat operator-(const HurwitzQuat &a, const HurwitzQuat &b) {
  return HurwitzQuat(a.s - b.s, a.x - b.x, a.y - b.y, a.z - b.z);
}
HurwitzQuat operator*(const HurwitzQuat &a, const HurwitzQuat &b) {
  long long s = a.s * b.s - a.x * b.x - a.y * b.y - a.z * b.z;
  long long x = a.s * b.x + b.s * a.x + a.y * b.z - a.z * b.y;
  long long y = a.s * b.y + b.s * a.y + a.z * b.x - a.x * b.z;
  long long z = a.s * b.z + b.s * a.z + a.x * b.y - a.y * b.x;
  assert(s % 2 == 0 && x % 2 == 0 && y % 2 == 0 && z % 2 == 0);
  return HurwitzQuat(s / 2, x / 2, y / 2, z / 2);
}
long long divclose(long long num, long long den) {
  if (den < 0) num = -num, den = -den;
  num = 2 * num + den, den = 2 * den;
  return num >= 0 ? num / den : (num - den + 1) / den;
}
pair<HurwitzQuat, HurwitzQuat> div(const HurwitzQuat &a, const HurwitzQuat &b) {
  HurwitzQuat num = conj(b) * a;
  long long den = norm(b);
  HurwitzQuat q;
  if (num.s % (2 * den) == 0 || num.s % den != 0 || num.x % (2 * den) == 0 ||
      num.x % den != 0 || num.y % (2 * den) == 0 || num.y % den != 0 ||
      num.z % (2 * den) == 0 || num.z % den != 0) {
    q = HurwitzQuat(2 * divclose(num.s, 2 * den), 2 * divclose(num.x, 2 * den),
                    2 * divclose(num.y, 2 * den), 2 * divclose(num.z, 2 * den));
  } else {
    q = HurwitzQuat(2 * divclose(num.s - den, 2 * den) + 1,
                    2 * divclose(num.x - den, 2 * den) + 1,
                    2 * divclose(num.y - den, 2 * den) + 1,
                    2 * divclose(num.z - den, 2 * den) + 1);
  }
  return make_pair(q, a - b * q);
}
HurwitzQuat gcd(const HurwitzQuat &a, const HurwitzQuat &b) {
  return norm(b) == 0 ? a : gcd(b, div(a, b).second);
}
const int MAXN = 10000;
int n;
long long x[MAXN], y[MAXN], z[MAXN];
long long ansnorm;
long long ansx[3], ansy[3], ansz[3];
HurwitzQuat a[MAXN];
void solve() {
  long long G = 0;
  HurwitzQuat g(0);
  for (int i = (0); i < (n); ++i) {
    a[i] = HurwitzQuat(0, 2 * x[i], 2 * y[i], 2 * z[i]);
    G = gcd(G, norm(a[i]));
    g = gcd(g, a[i]);
  }
  vector<long long> cand;
  for (long long x = 1; x * x * x <= G; ++x) {
    if (G % (x * x) == 0) cand.push_back(x);
    if (G % x == 0) {
      long long y = sqrt(G / x);
      if (y * y == G / x) cand.push_back(y);
    }
  }
  sort(cand.begin(), cand.end());
  cand.erase(unique(cand.begin(), cand.end()), cand.end());
  for (int i = ((int)(cand).size()) - 1; i >= 0; --i) {
    HurwitzQuat q = gcd(g, HurwitzQuat(2 * cand[i]));
    if (norm(q) != cand[i]) continue;
    bool ok = true;
    for (int j = (0); j < (n); ++j) {
      HurwitzQuat num = conj(q) * a[j] * q;
      long long den = norm(q) * norm(q);
      if (num.s % (2 * den) != 0 || num.x % (2 * den) != 0 ||
          num.y % (2 * den) != 0 || num.z % (2 * den) != 0) {
        ok = false;
        break;
      }
    }
    if (ok) {
      ansnorm = norm(q) * norm(q);
      for (int i = (0); i < (3); ++i) {
        HurwitzQuat e =
            q * HurwitzQuat(0, i == 0 ? 2 : 0, i == 1 ? 2 : 0, i == 2 ? 2 : 0) *
            conj(q);
        assert(e.s == 0 && e.x % 2 == 0 && e.y % 2 == 0 && e.z % 2 == 0);
        ansx[i] = e.x / 2, ansy[i] = e.y / 2, ansz[i] = e.z / 2;
      }
      return;
    }
  }
  assert(false);
}
void run() {
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) scanf("%lld%lld%lld", &x[i], &y[i], &z[i]);
  solve();
  printf("%lld\n", ansnorm);
  for (int i = (0); i < (3); ++i)
    printf("%lld %lld %lld\n", ansx[i], ansy[i], ansz[i]);
}
int main() {
  run();
  return 0;
}