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(|r1 − r2|, |g1 − g2|, |b1 − b2|) ≥ 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 N K D followed by N triplets ri gi bi, representing initial colors.

Output file format

Output file must contain K triplets rj gj bj, 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

0 ≤ ri, gi, bi ≤ 255 for both input and output colors,
0 ≤ N ≤ 256, 1 ≤ D, K ≤ 256

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.069s 0.011s 13