P16048 [ICPC 2022 NAC] Ranked Choice Spoiling

排名投票（Ranked choice voting）是一种确定选举获胜者的方法，其流程如下： 1. 每位候选人（本题中用 **A**、**B**、**C** 等标识）都被列在选票上。 2. 每位投票人对候选人从最喜欢到最不喜欢进行排序（例如，**B** 第一，**A** 第二，**C** 最后），并将该排序作为选票提交。 3. 收到所有选票后，统计当前仍在选票上的每位候选人的第一选择票数。如果有候选人的第一选择票数超过总票数的一半，则该候选人被宣布为获胜者。 4. 如果没有候选人的第一选择票数超过一半，则淘汰第一选择票数最少的候选人（如果有多位候选人并列最少，则淘汰字典序最大的候选人，例如 **C** 在 **B** 之前被淘汰），然后返回第 3 步，在剩余的候选人中继续计票。 **搅局**（Spoiling）是指一位额外的候选人 **Z** 加入竞选，从而使得胜者从某位原有候选人转变为另一位（不是 **Z** 的）原有候选人。排名投票的支持者声称，相比于更常见的简单多数投票（得票最多者获胜），这种选举方式更不容易出现搅局情况。 你是一位候选人 **A**，正与一位或两位其他候选人竞争。你想通过引入一位候选人 **Z** 来搅局并使你从中获益，以此来证明他们是错的。假设你知晓每位投票人对现有候选人的排序，并且你有能力设计候选人 **Z**，完全掌控每位投票人将 **Z** 插入其排序中的位置。对于给定的投票人排序集合，是否存在一种设计候选人 **Z** 的方式，使得 **Z** 搅局并使你从中受益？

第一行包含两个整数 $n$（$1 \le n \le 1{,}000$）和 $k$（$2 \le k \le 3$），其中 $n$ 是投票人数，$k$ 是现有候选人的数量。 接下来的 $n$ 行，每行包含 $k$ 个空格分隔的大写字母（**A**、**B** 或 **C**），表示每位投票人对候选人的排序，从最喜欢到最不喜欢。每行中每个候选人恰好出现一次（当 $k = 2$ 时，**C** 不存在）。

输出一个整数，如果存在一种方式设计候选人 **Z** 使得 **Z** 搅局并使候选人 **A** 受益（或者 **A** 已经能够赢得选举），则输出 $1$，否则输出 $0$。

翻译由 DeepSeek V3.2 完成