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.097s 0.014s 13