I. Кубическая решетка
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кубическая решетка $$$L$$$ в $$$3$$$-мерном евклидовом пространстве  — это множество точек, определенных следующим образом: $$$$$$L=\{u \cdot \vec r_1 + v \cdot \vec r_2 + w \cdot \vec r_3\}_{u, v, w \in \mathbb Z}$$$$$$ Где $$$\vec r_1, \vec r_2, \vec r_3 \in \mathbb{Z}^3$$$ это некоторые целочисленные векторы такие, что

  • $$$\vec r_1$$$, $$$\vec r_2$$$ и $$$\vec r_3$$$ попарно ортогональны: $$$$$$\vec r_1 \cdot \vec r_2 = \vec r_1 \cdot \vec r_3 = \vec r_2 \cdot \vec r_3 = 0$$$$$$ Здесь $$$\vec a \cdot \vec b$$$ обозначает скалярное произведение $$$\vec a$$$ и $$$\vec b$$$.
  • $$$\vec r_1$$$, $$$\vec r_2$$$ и $$$\vec r_3$$$ имеют одинаковую длину: $$$$$$|\vec r_1| = |\vec r_2| = |\vec r_3| = r$$$$$$
Вам дан набор $$$A=\{\vec a_1, \vec a_2, \dots, \vec a_n\}$$$ целочисленных точек, $$$i$$$-я точка имеет координаты $$$a_i=(x_i;y_i;z_i)$$$. Пусть $$$g_i=\gcd(x_i,y_i,z_i)$$$. Гарантируется, что $$$\gcd(g_1,g_2,\dots,g_n)=1$$$.

Вы должны найти кубическую решетку $$$L$$$ такую, чтобы $$$A \subset L$$$ и $$$r$$$ было максимально возможным.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^4$$$) — количество точек в $$$A$$$.

$$$i$$$-я из следующих $$$n$$$ строк содержит целые числа $$$x_i$$$, $$$y_i$$$, $$$z_i$$$ ($$$0 < x_i^2 + y_i^2 + z_i^2 \leq 10^{16}$$$) — координаты $$$i$$$-й точки.

Гарантируется, что $$$\gcd(g_1,g_2,\dots,g_n)=1$$$, где $$$g_i=\gcd(x_i,y_i,z_i)$$$.

Выходные данные

В первой строке выведите единственное целое число $$$r^2$$$, квадрат максимально возможного $$$r$$$.

В следующих $$$3$$$ строках выведите координаты векторов $$$\vec r_1$$$, $$$\vec r_2$$$ и $$$\vec r_3$$$ соответственно.

Если есть несколько возможных ответов, выведите любой.

Примеры
Входные данные
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