Gotta Catch 'Em All
면접 대비시간 제한2초메모리 제한512 MB
각 포켓몬의 좌표와 종류가 주어질 때, 최소 K가지 종류의 포켓몬을 포함하는 가장 작은 정사각형의 한 변 길이를 구합니다.
문제
애쉬 케첨은 세상의 포켓몬을 전부 잡으려는 포켓몬 트레이너이다. 그는 대부분을 이미 잡았고, 도감을 완성하려면 아직 없는 서로 다른 종류 K개가 더 필요하다.
애쉬는 2차원 격자 세계에 산다. 포켓몬은 정수 좌표에 나타나며, 같은 종류의 포켓몬이 여러 마리 있을 수 있다. 애쉬에게 필요한 것은 아무 포켓몬 K마리가 아니라 서로 다른 종류 K가지이다.
애쉬는 하늘에서 커다란 정사각형 그물을 던진다. 포켓몬은 그물 안이나 가장자리 위에 있으면 잡힌다. 정사각형의 각 변은 x축 또는 y축과 평행하다. 서로 다른 종류 K가지의 포켓몬을 포함하는 정사각형의 한 변 길이 중 최솟값을 구하라. 그물은 넓이가 양수여야 하므로 한 변의 길이는 양수여야 한다.
입력
첫 줄에 테스트 케이스의 개수 T가 정수 하나로 주어진다 ().
각 테스트 케이스는 정수 N과 K가 주어진 줄로 시작한다. N은 포켓몬의 수 (), K는 종류의 수 ()이다.
이어지는 N개의 줄에는 각각 정수 X, Y, Z가 공백으로 구분되어 주어진다. X는 포켓몬의 x좌표, Y는 y좌표, Z는 포켓몬의 종류이다. , , .
출력
각 테스트 케이스마다 서로 다른 종류 K가지의 포켓몬을 포함하는 정사각형의 한 변 길이 최솟값을 한 줄에 출력한다.