$$$3$$$ 维欧几里得空间中的立方晶格 $$$L$$$ 是按以下方式定义的一组点: $$$$$$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$$$$$$
你必须找到一个立方晶格 $$$L$$$ 使得 $$$A \subset L$$$ 和 $$$r$$$ 是可能的最大值。
输入
第一行包含单个整数 $$$n$$$ ($$$1 \leq n \leq 10^4$$$) — $$$A$$$ 中的点数。
以下 $$$n$$$ 行中的第 $$$i$$$ 包含整数 $$$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$$$的坐标。
如果有多个可能的答案,则输出任何一个。
示例
输入 #1
2 1 2 3 1 2 1
输出 #1
1 1 0 0 0 1 0 0 0 1
输入 #2
1 1 2 2
输出 #2
9 2 -2 1 1 2 2 -2 -1 2
输入 #3
1 2 5 5
输出 #3
9 -1 2 2 2 -1 2 2 2 -1