题目描述

排名投票（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$。

5 2
B A
A B
A B
B A
B A

1

1 3
A B C

1

8 3
A B C
B C A
B C A
B C A
C B A
C B A
C B A
C B A

0

提示

翻译由 DeepSeek V3.2 完成