배 현명한 투표

Bob Roberts는 과일 애호가 모임인 Pear-wise Club의 회장직을 마치려 한다. 회장 자리는 아주 좋은 자리라서 많은 사람이 출마했는데, Bob이 보기에 어떤 사람은 훌륭하고 어떤 사람은 형편없다. 고민 끝에 Bob은 후임자를 정하는 방식으로 순차적 일대일 투표를 사용하도록 Pear-wise Club의 규정을 개정했다.

순차적 일대일 투표는 다음과 같이 진행된다. 각 유권자는 후보를 가장 선호하는 순서부터 가장 덜 선호하는 순서까지 나열한 투표용지를 제출한다. 그다음 두 후보를 골라 이 투표용지로 일대일 대결을 치르는데, 각 투표용지에서 두 후보의 상대적 위치를 보고 각 유권자가 이 대결에서 누구에게 투표할지 정한다. 이 대결의 승자가 세 번째 후보와 두 번째 일대일 대결을 치르고, 그 승자가 네 번째 후보와 세 번째 대결을 치르는 식으로 이어진다. 선거의 승자는 마지막 일대일 대결의 승자다.

후보가 일대일 대결에 참여하는 순서는 의제로 정해지며, 의제는 미리 선택된 후보 순서다. 의제의 처음 두 후보가 첫 대결을 치르고, 그 승자가 의제의 세 번째 후보와 맞붙는 식으로 진행된다. 예를 들어 다섯 후보 A, B, C, D, E를 나열한 다음 13장의 투표용지가 있다고 하자.

(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이 의제를 정한다! 또한 모든 유권자의 선호를 알고 있으므로, 자신이 후임자로 바라는 사람이 당선되도록 하는 의제를 찾을 수 있다고 확신한다. 이를 확인하기 위해 Bob은 여러분에게 프로그램을 하나 작성해 달라고 한다. 투표용지 집합이 입력으로 주어지면, 각 후보에 대해 그 후보가 당선되는 의제가 존재하는지 판별하는 프로그램이다.

입력

입력의 첫 줄에는 두 양의 정수 n m (n ≤ 26, m ≤ 2 000)이 주어지며, 각각 후보 수와 서로 다른 투표용지 수다. 후보는 알파벳의 처음 n개 대문자로 표시된다. 다음 m개 줄에는 m개의 투표용지가 하나씩 주어진다. 각 줄은 그 투표용지를 제출한 유권자 수를 나타내는 양의 정수 p (p ≤ 100)로 시작하고, 이어서 투표용지를 나타내는 길이 n의 문자열이 주어진다. 이 대문자 문자열은 영어 알파벳의 처음 n개 문자를 순열로 나열한 것이며, 문자열의 첫 번째 문자가 그 투표용지에서 가장 선호하는 후보, 두 번째 문자가 두 번째로 선호하는 후보, 이런 식으로 이어진다. 모든 투표용지의 총 투표 수는 홀수이므로 어떤 일대일 투표에서도 동점이 날 수 없다.

출력

각 후보에 대해 후보의 문자 뒤에 콜론을 붙이고, 그 후보가 당선되는 의제가 존재하면 can win을, 그런 의제가 존재하지 않으면 can't win을 출력한다.