Bob Roberts 即将结束他在一个名为“梨子俱乐部”（Pear-wise Club）的水果爱好者组织的会长任期。担任会长是一个肥缺，因此有许多人竞选，Bob 觉得其中一些人很不错，而另一些人则令人讨厌。经过一番思考，Bob 修改了“梨子俱乐部”的章程，决定使用“顺序两两投票制”（sequential pairwise voting）来选出他的继任者。

顺序两两投票制的工作方式如下：每位选民提交一张选票，按从最喜欢到最不喜欢的顺序排列候选人。然后，从中选出两名候选人进行一对一的对决，利用每张选票上候选人的相对位置来决定每位选民在这次对决中的投票意向。这次对决的获胜者随后与第三名候选人进行一对一的对决；该对决的获胜者再与第四名候选人进行对决，以此类推。选举的获胜者即为最后一场一对一对决的获胜者。

候选人参加一对一对决的顺序由“议程”（agenda）决定，议程是预先选定的一组候选人排序。议程中的前两名候选人进行第一场对决；该对决的获胜者随后与议程中的第三名候选人对决，依此类推。例如，假设有 13 张选票，每张选票对 A、B、C、D 和 E 五名候选人进行排名：

(4) (3) (3) (2) (1) A D C B E D C A D B C A D C C B B B A D E E E E A

每张选票上方的数字表示提交该选票的选民人数。如果议程是 ABCDE，那么顺序两两投票制将按以下方式进行：在 A 和 B 的第一场对决中，A 以 10–3 获胜；随后 A 与 C（议程中的第三名候选人）对决，此时 C 以 9–4 获胜；接着 C 与 D 对决，D 以 9–4 获胜；最后 D 与 E 对决，D 以 12–1 获胜。因此，使用该议程，D 将成为最终获胜者。使用反向议程 EDCBA 将导致 A 赢得选举（细节留给读者自行推导）。

Bob 选择顺序两两投票制并非出于政治科学的原因，也不是因为其名称的巧合。他知道结果在很大程度上取决于所使用的议程，而作为现任会长，Bob 可以设定议程！由于他也了解每个人的投票偏好，他很有把握能找到一个议程，使得他偏好的继任者能够当选。为了确保这一点，他希望你编写一个程序，在给定一组选票作为输入时，确定对于每位候选人，是否存在一个议程能使其赢得选举。

输入格式

输入的第一行包含两个正整数 $n$ 和 $m$ ($n \le 26, m \le 2000$)，分别表示候选人数和唯一选票的数量。候选人以大写字母表的前 $n$ 个字母标记。接下来的 $m$ 行，每行显示 $m$ 张选票中的一张。每行以一个正整数 $p$ ($p \le 100$) 开头，表示提交该选票的选民人数，随后是一个包含 $n$ 个字符的字符串，指定了选票内容。该大写字符串是英语字母表前 $n$ 个字符的一个排列，字符串中的第一个字符表示选票中最受青睐的候选人，第二个字符表示次受青睐的候选人，以此类推。所有选票的总票数将为奇数，因此在任何两两对决中都不会出现平局。

输出格式

对于每位候选人，显示该候选人的字母，后跟一个冒号，然后是短语 can win（如果存在该候选人能获胜的议程）或 can't win（如果不存在这样的议程）。

样例

样例输入 1

5 5
4 ADCBE
3 DCABE
3 CADBE
2 BDCAE
1 EBCDA

样例输出 1

A: can win
B: can't win
C: can win
D: can win
E: can't win

样例输入 2

3 3
1 ABC
1 BCA
1 CAB

样例输出 2

A: can win
B: can win
C: can win