P6441 [COCI 2011/2012 #6] PASTELE

Mirko received a gift.

The gift contains $n$ crayons. The color of each crayon is made up of the three primary colors of light: red, green, and blue, represented by parameters $R_i, G_i, B_i$. The color of this crayon is determined by these three parameters. For two crayons $i, j$, we define their difference value as $\max(|R_i-R_j|, |G_i-G_j|, |B_i-B_j|)$. We define the color value of a set of crayons as the maximum difference value among any pair of crayons in this set. Given the parameters of these $n$ crayons, find $k$ crayons such that the color value is minimized.

The first line contains two integers $n, k$. The next $n$ lines each contain three integers $R_i, G_i, B_i$, representing the color parameters of the $i$-th crayon.

The first line outputs one integer, the minimum possible color value of the selected $k$ crayons. The next $k$ lines each contain three integers, describing which crayons make up these $k$ crayons. **Since the composition of the solution may not be unique, this problem uses SPJ**.

#### Constraints - For $50\%$ of the testdata, $R_i, G_i, B_i \le 20$ is guaranteed. - For another $30\%$ of the testdata, $R_i, G_i, B_i \le 50$ is guaranteed. - For $100\%$ of the testdata, $2 \le k \le n \le 10^5$, $0 \le R_i, G_i, B_i \le 256$, $0 \le k_i \le m$. #### Hint Please pay attention to the impact of constant factors on program efficiency. #### Notes **This problem is translated from [COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #6](https://hsin.hr/coci/archive/2011_2012/contest6_tasks.pdf) *T5 PASTELE***. Translated by ChatGPT 5