Description

本题灵感来源于 Sid Sackson 设计的桌游 Can't Stop。本题与该游戏有相似之处，但不要求你玩过 Can't Stop。

你正在玩一款（非常大）的桌面游戏。在这款游戏中，你会得到一个长度为 $N$ 的掷骰子序列。每组掷骰包含 $D$ 次骰子，每次掷骰得到一个整数。

你要赢得游戏，需要找到序列中最长的“超级棒区间”。一个区间指的是若干连续的掷骰组。如果存在 $k$ 个数字，使得该区间内的每一组掷骰都至少包含这 $k$ 个数字中的一个，则称该区间是“超级棒”的。

例如，假设 $D=2$，$k=3$，掷骰组如下：

第 0 组: 10 20
第 1 组: 50 60
第 2 组: 70 30
第 3 组: 40 40
第 4 组: 30 30
第 5 组: 20 40

区间 $[0,2]$（第 0 组到第 2 组）是超级棒的，因为第 $0\sim 2$ 组都包含 $10, 50, 70$ 这三个数中的至少一个。区间 $[1,5]$ 是超级棒的，因为第 $1\sim 5$ 组都至少包含 $50, 30, 40$ 这三个数中的一个。这个区间包含 5 组掷骰，是最长的超级棒区间。

你的任务是输出最长超级棒区间的起止下标。如果有多个同样长度的超级棒区间，输出起始下标最小的那一个。注意，第一组掷骰编号为 0。

Input Format

第一行为测试用例数 $T$。接下来的 $T$ 组数据，每组数据第一行为三个用空格分隔的整数 $N$、$D$、$k$，含义如上。下一行有 $N \times D$ 个整数。前 $D$ 个整数是第 0 组的结果，接下来的 $D$ 个整数是第 1 组的结果，依此类推。

Output Format

对于每个测试用例，输出一行 "Case #x: y z"，其中 $x$ 为测试用例编号（从 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

Hint

限制条件

• $1 \leq T \leq 100$
• $1 \leq D \leq 4$
• $1 \leq \text{每次掷骰结果} \leq 10^5$
• 有 6 个测试点满足 $1 \leq N \leq 10^5$
• 其他测试点满足 $1 \leq N \leq 10^3$

小数据集（11 分，测试集 1 - 可见）

• 时间限制：60 6 秒
• $k = 2$

大数据集（32 分，测试集 2 - 隐藏）

• 时间限制：120 12 秒
• $2 \leq k \leq 3$

翻译由 ChatGPT-4.1 完成。