Can't Stop (Small)

이 문제는 Sid Sackson이 만든 보드게임 Can't Stop에서 아이디어를 가져왔다. 이 게임을 해 본 적이 없어도 문제를 푸는 데는 상관없다.

아주 큰 보드게임을 하고 있다. 이 게임은 주사위 묶음 $N$개를 순서대로 준다. 주사위 묶음 하나는 주사위 눈 $D$개로 이루어지고, 주사위 눈은 모두 정수다.

게임에서 이기려면 이 수열에서 가장 긴 완전 멋진 구간을 찾아야 한다. 구간은 연속한 주사위 묶음의 나열이다. 어떤 수 $k$개가 있어서 구간에 속한 모든 주사위 묶음이 그 $k$개 중 적어도 하나를 포함하면, 그 구간을 완전 멋진 구간이라고 부른다.

$D = 2$, $k = 3$이고 주사위 묶음이 다음과 같은 경우를 보자.

0번 묶음부터 2번 묶음까지의 구간은 0번, 1번, 2번 묶음이 모두 10, 50, 70 중 하나를 포함하므로 완전 멋진 구간이다. 1번 묶음부터 5번 묶음까지의 구간은 1번부터 5번까지의 묶음이 모두 50, 30, 40 중 하나를 포함하므로 완전 멋진 구간이다. 이 구간은 주사위 묶음 5개를 담고 있고, 이 수열에서 이보다 더 긴 완전 멋진 구간은 없다.

가장 긴 완전 멋진 구간의 첫 묶음 번호와 마지막 묶음 번호를 출력한다. 길이가 같은 완전 멋진 구간이 여럿이면 첫 번호가 가장 작은 구간을 출력한다. 첫 주사위 묶음의 번호는 0이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 테스트 케이스 $T$개가 주어진다. 각 테스트 케이스의 첫째 줄에는 세 정수 $N$, $D$, $k$가 공백으로 구분되어 주어진다. 다음 줄에는 정수 $N \times D$개가 주어진다. 앞의 $D$개는 첫 번째 주사위 묶음의 눈이고, 그다음 $D$개는 두 번째 주사위 묶음의 눈이며, 나머지도 같은 방식으로 이어진다.

제한

• $1 \le T \le 100$
• $1 \le D \le 4$
• $1 \le k \le 3$
• 주사위 눈은 모두 1 이상 $10^5$ 이하의 정수다.
• $1 \le N \le 10^5$인 테스트 케이스는 최대 6개다. 나머지 테스트 케이스에서는 $1 \le N \le 10^3$이다.

각 테스트 케이스마다 Case #x: y z 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y와 z는 가장 긴 완전 멋진 구간의 첫 번호와 마지막 번호다. 길이가 같은 구간이 여럿이면 첫 번호가 가장 작은 구간을 기준으로 한다.

보드게임 Can't Stop은 Sid Sackson이 디자인했고, 여러 출판사가 발매했다. Sid Sackson과 각 출판사는 이 문제를 후원하지 않으며 이 문제와 아무 관련이 없다.