排序选择投票（Ranked choice voting）是一种确定选举获胜者的方法，其流程如下：

1. 每位候选人（在本题中标识为 A, B, C 等）都被列在选票上。
2. 每位选民按从最喜欢到最不喜欢的顺序对候选人进行排名（例如：先选 B，再选 A，最后选 C），并提交该排名作为他们的投票。
3. 一旦收到所有选票，统计每位留在选票上的候选人的第一选择票数。如果某位候选人的第一选择票数超过半数，则该候选人被宣布为获胜者。
4. 如果没有候选人的第一选择票数超过半数，则将第一选择票数最少的候选人从选票中淘汰，并将过程返回到第 3 步，对剩余的候选人进行统计。（如果有多个这样的候选人，则淘汰字典序最靠后的候选人，例如，C 会比 B 先被淘汰。）

“破坏”（Spoiling）是指一名额外的候选人 Z 加入竞选，从而导致获胜者从现有的某位候选人变为另一位候选人（且该候选人不是 Z）。排序选择投票的支持者声称，这种选举方式比更常见的多数票制（得票最多的候选人获胜）更不容易受到“破坏”的影响。

你是选举中的候选人 A，你的对手是一到两名其他候选人。你希望通过安排一名候选人 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 来破坏选举并使候选人 A 获胜（或者如果 A 本来就会赢得选举），则输出 1，否则输出 0。

样例

样例输入 1

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

样例输出 1

1

样例输入 2

1 3
A B C

样例输出 2

1

样例输入 3

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

样例输出 3

0