题目描述

你在人马座的三叶星云里，发现了一类新生物：球状精灵。

球状精灵是一类外形为标准椭球形的精灵。每只精灵有三个维度的幅度 $\{r_1,r_2,r_3\}$，分别表示其三维世界中三个方向上的尺度。

而关于球状精灵有一个传说：族群中声望值最高的球状精灵会获得升入四维宇宙的机会。而某个幅度为 $\{r_1,r_2,r_3\}$ 的球状精灵的声望值 $\rho$ 定义为：

$$\rho=\left\lfloor{\frac{1}{4}\min\{r_1,r_2,r_3\}^3}\right\rfloor $$

其中 $\left\lfloor\right\rfloor$ 表示下取整。

同时，每只球状精灵可以选择与别的精灵拥抱至多一次，之后两者会合成为一个新的球状精灵。两只球状精灵能够拥抱，当且仅当它们存在至少一个幅度面能够重合。具体来讲，即需要两只精灵的幅度存在至少两个值相同。

例如，两只精灵三个方向上的幅度分别为 $\{a,x,y\}$ 和 $\{b,x,y\}$，那么他们可以选择拥抱并生成一只幅度为 $\{a+b,x,y\}$ 的新精灵。但是注意，精灵们都是漂浮在宇宙中的，所以他们可以任意旋转。比如幅度为 $\{x,y,z\}$ 的精灵可以任意旋转成为 $\{x,z,y\},\{z,x,y\},\{z,y,x\},\{y,z,x\},\{y,x,z\}$ 的精灵。拥抱形成的新精灵不能再次参与拥抱。

现在球状精灵们想知道，族群中能够升入四维宇宙的精灵，声望值最高能是多少？

请仔细阅读输入格式和输出格式以获取更详细的讯息。

输入格式

第 $1$ 行共一个正整数 $n$，表示族群中最初的球状精灵数目。最初全部的球状精灵都没有拥抱过。

第 $2\sim n+1$ 行，每行三个非负整数 $r_{i,1},r_{i,2},r_{i,3}$，分别表示编号为 $i$ 的球状精灵三个维度的幅度。

输出格式

第一行，输出一个整数 $opt$:

• 当最优情况下，升入四维空间的球状精灵是最初未拥抱过的精灵之一时，$opt=0$。

• 当最优情况下，升入四维空间的精灵是由原来的两只精灵拥抱生成时，$opt=1$。

第二行，有两种情况：

• 当 $opt=0$ 时，输出一个整数 $i$，表示升入四维空间的精灵是编号为 $i$ 的精灵。

• 当 $opt=1$ 时，输出两个整数 $i,j$，表示最终升入四维空间的精灵由编号为 $i,j$ 的精灵拥抱生成。

第三行，共一个整数，表示最优情况下升入四维空间精灵的声望值为多少。

如果最优解有多种方案，输出任意一种情况即可。

4
1 3 5
1 2 3
2 2 3
4 3 5

0
4
6

10
2 5 5
4 3 3
1 3 2
3 4 3
3 2 5
3 4 3
2 3 4
4 5 5
2 3 4
5 3 4

1
1 8
31

提示

对于 $10\%$ 的数据，$1\leq n\leq 20$。

对于 $40\%$ 的数据，$1\leq n\leq 800$。

对于 $70\%$ 的数据，$1\leq n\leq 5000$。

对于 $85\%$ 的数据，$1\leq n\leq 10^5$。

对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^5$，$1\leq r_{i,1},r_{i,2},r_{i,3} \leq 10^3$。