Processing math: 100%

Problem D. Distinct colors

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

Colors on computer screen are represented by (r,g,b) triplets, where r,g,b are integer intensities of red, green and blue components.

Two colors (r1,g1,b1) and (r2,g2,b2) are distinct if min(|r1r2|,|g1g2|,|b1b2|)D.

Your program will be given N (not necessarily distinct) colors. It must either calculate K new colors that are distinct from each other and from all initial colors, or determine that it is impossible.

Input file format

Input file contains numbers NKD followed by N triplets rigibi, representing initial colors.

Output file format

Output file must contain K triplets rjgjbj, representing resulting distinct colors. If there is no solution, output must contain a single number 1. If there is more than one solution, output any of them.

Constraints

0ri,gi,bi255 for both input and output colors,
0N256, 1D,K256

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 1 10
255 100 100
100 100 255
110 110 110
2
2 1 200
255 100 100
100 100 255
-1

0.064s 0.009s 13