P8585 The Legend of Spherical Sprites

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.

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$.

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.

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