Can't Stop (Large)

이 문제는 시드 잭슨(Sid Sackson)이 만든 보드게임 Can't Stop에서 아이디어를 얻었다. 게임을 해 본 적이 없어도 문제를 푸는 데는 아무 지장이 없다.

아주 큰 판에서 하는 게임을 한다고 하자. 이 게임에서는 굴림 묶음 $N$개가 순서대로 주어진다. 각 굴림 묶음은 주사위 굴림 $D$개로 이루어지고, 굴림 하나하나는 정수다.

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

예를 들어 $D=2$, $k=3$이고 굴림 묶음이 다음과 같다고 하자.

묶음 0부터 묶음 2까지의 구간은 세 묶음이 모두 10, 50, 70 중 하나를 포함하므로 완전 멋진 구간이다. 묶음 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$ 이상 $10^5$ 이하의 정수다.
• 테스트 케이스 6개는 $1 \le N \le 10^5$이고, 나머지 테스트 케이스는 모두 $1 \le N \le 10^3$이다.
• $2 \le k \le 3$

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

보드게임 Can't Stop은 시드 잭슨이 디자인했고 여러 회사가 출판했다. 잭슨과 출판사는 이 문제를 보증하지 않으며 이 문제와 아무 관련이 없다.