Problem Description

Mirko has received a gift consisting of $n$ crayons. Each crayon's color is determined by the three primary colors: red, green, and blue, represented by parameters $R_i, G_i, B_i$. The color of each crayon is determined by these three parameters.

For two crayons $i$ and $j$, we define their difference value as $\max(|R_i - R_j|, |G_i - G_j|, |B_i - B_j|)$. The color value of a set of crayons is defined as the maximum difference value among any two crayons in the set.

Given the characteristics of these $n$ crayons, find $k$ crayons such that the color value is minimized.

Input Format

The first line of input contains two integers $n$ and $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 of output should contain a single integer, representing the minimum color value of the $k$ crayons.

The next $k$ lines should each contain three integers, describing which $k$ crayons are chosen.

Since there may be multiple valid solutions, this problem uses a special judge (SPJ).

Sample Input and Output

Sample Input #1

2 2
1 3 2
2 6 4

Sample Output #1

3
1 3 2
2 6 4

Sample Input #2

3 2
3 3 4
1 6 4
1 1 2

Sample Output #2

2
3 3 4
1 1 2

Sample Input #3

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

Sample Output #3

2
6 2 7
4 1 5
6 2 6

Notes

Data Constraints

• For $50\%$ of the test cases, $R_i, G_i, B_i \le 20$.
• For another $30\%$ of the test cases, $R_i, G_i, B_i \le 50$.
• For $100\%$ of the test cases, $2 \le k \le n \le 10^5$, $0 \le R_i, G_i, B_i \le 256$, $0 \le k_i \le m$.

Hints

Please be aware of the impact of constant factors on the efficiency of your program.

Source

Translated from COCI2011-2012 CONTEST #6 T5 PASTELE.

见题面 Input 部分

见题面 Output 部分