Can't Stop (Small)

Time limit5sMemory limit512 MB

Summary

Find the longest consecutive run of roll sets where every set contains at least one of k chosen numbers.

Level: Medium6 of 10
Topics: Sliding window, Backtracking
Solved: No attempts yet

Problem

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

You are playing a very large board game. The game hands you a sequence of $N$ roll sets. Each roll set holds $D$ die rolls, and every die roll is an integer.

To win the game you have to find the largest totally awesome interval of the sequence. An interval is any run of consecutive roll sets. An interval is totally awesome if there are $k$ numbers such that every roll set in the interval contains at least one of those $k$ numbers.

Take $D = 2$ , $k = 3$ and these roll sets:

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

The interval from set 0 to set 2 is totally awesome, because sets 0, 1 and 2 all contain 10, 50 or 70. The interval from set 1 to set 5 is totally awesome, because sets 1 through 5 all contain 50, 30 or 40. That interval holds 5 roll sets, and no totally awesome interval of this sequence is longer.

Print the indices of the first and the last roll set of the longest totally awesome interval. When several totally awesome intervals reach that length, print the one whose first index is smallest. The first roll set has index 0.

Input

The first line holds the number of test cases $T$ . The $T$ test cases follow. Each test case starts with three integers $N$ , $D$ and $k$ separated by spaces. The next line holds $N \times D$ integers. The first $D$ integers are the rolls of the first roll set, the next $D$ integers are the rolls of the second roll set, and so on.

Limits

$1 \le T \le 100$
$1 \le D \le 4$
$1 \le k \le 3$
Every die roll is an integer between 1 and $10^5$ .
At most 6 test cases have $1 \le N \le 10^5$ . Every other test case has $1 \le N \le 10^3$ .

Output

For each test case, print one line holding 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. Ties are broken by the smallest first index.

Hint

The board game Can't Stop was designed by Sid Sackson, and several publishers have released it. Neither Sid Sackson nor any of those publishers endorses this problem or is involved with it.

Examples2

Example 1

Input

4
8 1 2
1 2 3 2 4 5 4 6
4 3 2
1 2 3 4 5 6 7 8 9 10 11 12
6 2 3
10 20 50 60 70 30 40 40 30 30 20 40
10 1 3
2 4 3 1 4 5 3 1 1 2

Expected output

Case #1: 1 3
Case #2: 0 1
Case #3: 1 5
Case #4: 1 4

Example 2
Input
```
1
1 1 1
7
```
Expected output
```
Case #1: 0 0
```