Problem Description

In the Trifid Nebula in Sagittarius, you discovered a new kind of creature: spherical sprites.

A spherical sprite is a sprite whose shape is a standard ellipsoid. Each sprite has three-dimensional radii $\{r_1,r_2,r_3\}$, which represent its scale along the three directions in the 3D world.

There is a legend about spherical sprites: the one with the highest prestige in the tribe will get a chance to ascend into the four-dimensional universe. The prestige value $\rho$ of a spherical sprite with radii $\{r_1,r_2,r_3\}$ is defined as:

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

where $\left\lfloor\right\rfloor$ denotes the floor function.

Also, each spherical sprite may choose to hug at most once with another sprite. After that, the two sprites will merge into one new spherical sprite. Two spherical sprites can hug if and only if they have at least one radius face that can coincide. More specifically, the radii of the two sprites must have at least two equal values.

For example, if the three radii of two sprites are $\{a,x,y\}$ and $\{b,x,y\}$, then they can choose to hug and create a new sprite with radii $\{a+b,x,y\}$. Note that sprites are floating in space, so they can rotate freely. For instance, a sprite with radii $\{x,y,z\}$ can be rotated into $\{x,z,y\},\{z,x,y\},\{z,y,x\},\{y,z,x\},\{y,x,z\}$. A new sprite formed by hugging cannot participate in hugging again.

Now the spherical sprites want to know: among all sprites that can ascend into the four-dimensional universe, what is the maximum possible prestige value?

Please read the input and output formats carefully for more detailed information.

Input Format

The first line contains one positive integer $n$, the number of spherical sprites in the tribe initially. Initially, none of the sprites has hugged.

Lines $2$ to $n+1$ each contain three non-negative integers $r_{i,1},r_{i,2},r_{i,3}$, representing the three radii of spherical sprite $i$.

Output Format

The first line outputs an integer $opt$:

• If, in the optimal case, the spherical sprite that ascends into four-dimensional space is one of the original sprites that has not hugged, then $opt=0$.
• If, in the optimal case, the sprite that ascends into four-dimensional space is formed by hugging two original sprites, then $opt=1$.

The second line has two cases:

• If $opt=0$, output one integer $i$, meaning the sprite that ascends is sprite $i$.
• If $opt=1$, output two integers $i,j$, meaning the final ascending sprite is formed by a hug between sprites $i$ and $j$.

The third line outputs one integer, the prestige value of the sprite that ascends into four-dimensional space in the optimal case.

If there are multiple optimal solutions, output any one of them.

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

Hint

For $10\%$ of the testdata, $1\leq n\leq 20$.

For $40\%$ of the testdata, $1\leq n\leq 800$.

For $70\%$ of the testdata, $1\leq n\leq 5000$.

For $85\%$ of the testdata, $1\leq n\leq 10^5$.

For $100\%$ of the testdata, $1\leq n\leq 5\times 10^5$, $1\leq r_{i,1},r_{i,2},r_{i,3} \leq 10^3$.

Translated by ChatGPT 5