题目描述

这个问题是源于一个在棋盘上玩的，由 Sid Sackson 设计的名叫 Can't stop 的游戏的。这个问题与 Can't stop 有一定的相似之处，但是不需要玩过 Can't stop。

你在玩一个（非常大型的）棋盘游戏。在这个游戏里面，给出了一个长度为 $N$ 的 roll set 的序列。每个 roll set 包括 $D$ 个 die roll，每个 die roll 是一个正整数。

你需要找到序列中总长度最大的极好的区间。区间即为连续的一段 roll set。如果存在 $k$ 个数使某个区间内的所有 roll set 都至少包含其中一个，那么，这个区间就被认为是极好的。

例如：$d=2,k=3$ 时，roll set 如下：

$$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$ 中的每个 roll set 都包含了 $10$，$50$ 或 $70$。从 $1$ 到 $5$ 的区间也是极好的，因为 $1$ 到 $5$ 的所有 roll set 都包含 $50$，$30$ 或 $40$。它包含了 $5$ 个 roll set，是总长度最大的极好的区间。

你的任务是输出总长度最大的极好的区间的第一个元素的下标和最后一个元素的下标。如果有多个长度一样的，输出第一个元素下标最小的。请注意下标从 $0$ 开始。

输入格式

本题有多组数据。

第一行包含一个整数 $T$，表示数据组数。接下来 $T$ 组数据。

每组数据的第一行是三个正整数 $N,D,k$，描述如上。接下来一行，包含 $N\times D$ 个整数，前 $D$ 个整数表示第一个 roll set，接下来 $D$ 个表示第二个 roll set，以此类推。

输出格式

对于每个 case，输出一行，Case #x: y z，$x$ 表示 case 标号（从 $1$ 开始），$y$ 和 $z$ 是答案区间的第一个和最后一个元素的下标。

样例

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

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

数据规模与约定

对于 $45\%$ 的数据，$N\le 1000$。

对于 $50\%$ 的数据，$k=2$。

前两部分数据共计 $70\%$。

对于 $100\%$ 的数据，$2\le k\le 3$，$T=10$，$1 \le D \le 4$，$1 \le$ 每个die roll $\le 10^5$。

输入文件在 4.8MB 以内。

对于每组测试点，最多存在 $6$ 个 case 存在 $1 \le N \le 10^5$，对于其他所有的 case，$1 \le N \le 10^3$。