P13621 [ICPC 2024 APC] Personality Test

有 $n$ 名学生正在参加一个包含 $m$ 个问题的人格测试。学生编号为 $1$ 到 $n$，问题编号为 $1$ 到 $m$。对于每个问题，每名学生可以用一个大写拉丁字母（`A`-`Z`）作答，也可以不作答。设 $S_i$ 是一个长度为 $m$ 的字符串，代表学生 $i$ 的答案，其中 $S_i$ 的第 $j$ 个字符如果是一个大写拉丁字母，表示他们回答了问题 $j$；如果是一个句点（`.`），表示他们没有回答。 如果存在一个包含至少 $k$ 个问题的集合，满足以下条件，则两名学生被认为是**相似的**：两名学生都回答了该集合中的所有问题，并且对于该集合中的每个问题，他们的答案都相同。 例如，设 $n=3, m=3, k=2, S_1=$`BBC`$, S_2=$`..C`, 并且 $S_3=$`.BC`。在这个例子中，学生 $1$ 和 $3$ 是相似的，因为他们对问题 $2$ 和 $3$ 的回答相同；而学生 $2$ 和 $3$ 不相似，因为他们仅对问题 $3$ 的回答相同。 你需要找到一对整数 $(a, b)$，满足 $a < b$ 且学生 $a$ 和 $b$ 是相似的；或者确定不存在这样的配对。如果存在多对，请找出 $b$ 最小的那一对。如果仍然存在多对，请找出 $a$ 最大的那一对。

输入的第一行包含三个整数 $n$，$m$ 和 $k$ ($2 < n < 5000$; $1 \le m \le 3000$; $1 < k < 5$)。 接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串。第 $i$ 行包含字符串 $S_i$。

输出一行，包含题目描述中提到的代表相似学生对的整数 $a$ 和 $b$；如果不存在这样的配对，则只输出整数 $-1$。

**样例解释 #1** 这就是题目描述中的例子。 **样例解释 #2** 学生 $1$ 和 $2$ 是相似的。 **样例解释 #3** 不存在相似的学生。