Кубическая решетка \(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\) было максимально возможным.
Выходные данные
В первой строке выведите единственное целое число \(r^2\), квадрат максимально возможного \(r\).
В следующих \(3\) строках выведите координаты векторов \(\vec r_1\), \(\vec r_2\) и \(\vec r_3\) соответственно.
Если есть несколько возможных ответов, выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2 3
1 2 1
|
1
1 0 0
0 1 0
0 0 1
|
|
2
|
1
1 2 2
|
9
2 -2 1
1 2 2
-2 -1 2
|
|
3
|
1
2 5 5
|
9
-1 2 2
2 -1 2
2 2 -1
|