프로그램 명: coci_pastele(special judge)
제한시간: 5 초
미르코는 최근에 N개의 색연필을 선물로 받았다. 한 색연필의 색깔은 세 가지 색 (빨간색, 초록색, 파란색) 의 혼합으로 나타낼 수 있다. i번째 색연필의 색깔은 세 개의 정수 Ri (빨간색), Gi (초록색), Bi (파란색)로 표현된다.
i번째 색연필과 j번째 색연필의 차이는 Max(|Ri - Rj|, |Gi - Gj|, |Bi - Bj|)이다. 색연필의 부분열의 채색도는 그 부분열의 임의의 두 색연필간의 차이 중 최댓값과 같다.
미르코는 길이 K의 색연필 부분열 중에서 가장 작은 채색도를 가진 것을 구하고자 한다. 이 부분열은 연속적일 필요가 없다.
입력
입력의 첫 번째 줄에는 두 정수 N과 K가 주어진다 (2 ≤ K ≤ N ≤ 100 000). 그 다음에는 N개의 줄이 입력되는데, N개의 줄 중에서 i번째 줄에는 세 정수 Ri, Gi, Bi가 주어진다 (0 ≤ Ri, Gi, Bi ≤ 255).
출력
출력의 첫 번째 줄에는 길이 K의 부분열이 가질 수 있는 최소의 채색도가 있어야 한다. 연 이은 K줄에는 부분열의 색연필의 R, G, B값이 있어야 한다. 어떤 순서로 출력해도 되며, 최소의 채색도를 갖는 모든 부분열은 정답으로 인정된다.
Mirko recently got N crayons as a gift. The color of each crayon is a combination of three primary colors: red, green and blue. The color of the ith crayon is represented with three integers: Ri for the red, Gi for the green and Bi for the blue component.
The difference between the ith and the jth crayon is max(|Ri - Rj|, |Gi - Gj|, |Bi - Bj|). The colorfulness of a subsequence of crayons is equal to the largest difference between any two crayons in the subsequence.
Mirko needs a subsequence with K crayons with the smallest colorfulness for his drawing. The subsequence does not have to be consecutive. Find it!
입력
The first line of input contains integers N and K (2 ≤ K ≤ N ≤ 100 000).
The ith of the folowing N lines contains three integers Ri, Gi and Bi (0 ≤ Ri, Gi, Bi ≤ 255).
출력
The first line of output should contain the smallest colorfulness of a subsequence with K crayons.
The following K lines should contain the R, G and B values of the colors of the crayons in the subsequence, in any order. Any subsequence that yields the smallest colorfulness will be accepted.
입출력 예
input
2 2
1 3 2
2 6 4
output
3
1 3 2
2 6 4
input
3 2
3 3 4
1 6 4
1 1 2
output
2
3 3 4
1 1 2
input
5 3
6 6 4
6 2 7
3 1 3
4 1 5
6 2 6
output
2
6 2 7
4 1 5
6 2 6
출처:coci 2012 5/6
번역+special judge:ryanch1
[질/답]
[제출 현황]
[푼 후(0)]