Description

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.

Input Format

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.

Output Format

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.

2 2
1 3 2
2 6 4

3
1 3 2
2 6 4

3 2
3 3 4
1 6 4
1 1 2

2
3 3 4
1 1 2

5 3
6 6 4
6 2 7
3 1 3
4 1 5
6 2 6

2
6 2 7
4 1 5
6 2 6

Hint

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 CONTEST #6 T5 PASTELE.

Translated by ChatGPT 5