Can't Stop (Large)

This problem takes its idea from Can't Stop, a board game designed by Sid Sackson. You do not need to have played Can't Stop to solve it.

You are playing a game on a very large board. The game gives you $N$ roll sets in order. Each roll set consists of $D$ die rolls, and every die roll is an integer.

To win the game you have to find the longest totally awesome interval of the sequence. An interval is any run of consecutive roll sets. An interval is called totally awesome if you can pick $k$ numbers such that every roll set in the interval contains at least one of them.

For example, suppose $D=2$, $k=3$, and the roll sets are these.

The interval from set 0 to set 2 is totally awesome, because all three sets contain 10, 50 or 70. The interval from set 1 to set 5 is also totally awesome, because all five sets contain 50, 30 or 40. That interval holds 5 roll sets, and it is the longest totally awesome interval.

Output the indices of the first and the last roll set of the longest totally awesome interval. If several totally awesome intervals have that length, pick the one with the lowest first index. The first roll set has index 0.

The first line of the input gives the number of test cases $T$. $T$ test cases follow. The first line of each test case holds three space separated integers $N$, $D$ and $k$. The next line holds $N \times D$ integers. The first $D$ of them are the rolls of the first roll set, the next $D$ are the rolls of the second roll set, and so on.

Limits

• $1 \le T \le 100$
• $1 \le D \le 4$
• Every die roll is an integer between $1$ and $10^5$.
• For 6 test cases, $1 \le N \le 10^5$. For all the other test cases, $1 \le N \le 10^3$.
• $2 \le k \le 3$

For each test case, output one line containing "Case #x: y z", where x is the test case number starting from 1, and y and z are the first and the last index of the longest totally awesome interval. If several intervals have that length, output the one with the lowest first index.

The board game Can't Stop was designed by Sid Sackson and has been published by many publishers. Neither Mr. Sackson nor any of the publishers endorses this problem or has any involvement with it.