멈출 수 없어

이 문제는 Sid Sackson가 설계한 보드게임 Can't Stop에서 영감을 받았다. 이 문제는 비슷한 발상을 사용하지만, 여러분이 Can't Stop를 해 보았다고 가정하지 않는다.

여러분은 매우 큰 보드게임을 하고 있다. 이 게임에서는 N개의 굴림 세트로 이루어진 수열이 주어진다. 각 굴림 세트는 D번의 주사위 굴림으로 구성된다. 각 주사위 굴림의 결과는 정수이다.

게임에서 이기려면 수열에서 가장 긴 완전히 멋진 구간을 찾아야 한다. 구간은 연속한 임의의 굴림 세트 수열이다. 어떤 k개의 수가 존재하여 구간 안의 모든 굴림 세트가 그 k개의 수 중 적어도 하나를 포함하면, 그리고 그럴 때에만 그 구간을 완전히 멋지다고 한다.

예를 들어, D=2이고 k=3이며 굴림 세트가 다음과 같다고 하자.

Set 0: 10 20
Set 1: 50 60
Set 2: 70 30
Set 3: 40 40
Set 4: 30 30
Set 5: 20 40

세트 0부터 세트 2까지의 구간은 굴림 세트 0-2가 모두 10, 50, 또는 70 중 하나를 포함하므로 완전히 멋지다. 세트 1부터 세트 5까지의 구간은 굴림 세트 1-5가 모두 50, 30, 또는 40 중 하나를 포함하므로 완전히 멋지다. 이 구간에는 5개의 굴림 세트가 포함되며, 가장 긴 완전히 멋진 구간이다.

가장 긴 완전히 멋진 구간에서 첫 굴림 세트와 마지막 굴림 세트의 인덱스를 출력해야 한다. 그 길이의 완전히 멋진 구간이 여러 개라면 첫 인덱스가 가장 작은 구간의 인덱스들을 출력한다. 첫 굴림 세트의 인덱스는 0임에 유의한다.

제한

메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ D ≤ 4. 1 ≤ 모든 주사위 굴림 ≤ $10^{5}$. 6개의 테스트 케이스에 대해, 1 ≤ N ≤ $10^{5}$. 그 밖의 모든 테스트 케이스에 대해, 1 ≤ N ≤ $10^{3}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 60초. k = 2.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 120초. 2 ≤ k ≤ 3.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 공백으로 구분된 세 정수 N, D, k로 시작한다. 다음 줄에는 N*D개의 정수가 주어진다. 처음 D개의 정수는 첫 번째 굴림 세트의 굴림 결과이고, 두 번째 D개의 정수는 두 번째 굴림 세트의 굴림 결과이며, 이후에도 같은 방식으로 이어진다.

각 테스트 케이스마다 "Case #x: y z"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, y와 z는 위에서 설명한 가장 긴 완전히 멋진 구간에서 첫 굴림 세트와 마지막 굴림 세트의 인덱스이다. 동률이면 가장 작은 첫 인덱스를 사용한다.

보드게임 Can't Stop는 Sid Sackson가 설계했으며, 여러 출판사가 출판했다. Neither Mr. Sackson과 어떤 출판사도 Google Code Jam를 보증하거나 이에 관여하지 않는다.