407433: GYM102788 K Tower of Hanoi

In an effort to master their skills, participants in the programming championship regularly solve the "Tower of Hanoi" problem. All teams use the standard classical algorithm of moving, consisting of $$$2^N-1$$$ moves.

Procedure Hanoi (X, Y, Z: char; N: integer); 
Begin 
 If N>0 then  
    Begin 
       Hanoi (X, Z, Y, N-1); 
       Writeln('Disk ', N, ' from ', X, ' to ', Y); 
       Hanoi (Z, Y, X, N-1) 
    End 
End; 

We have the intermediate results that some teams have achieved. All results are represented as rows of length $$$N$$$ (the number of disks), where element $$$i$$$ of the string is the symbol denoting the rod on which disk $$$i$$$ is located. For instance, let $$$N = 4$$$. Then the record $$$"BBCA"$$$ means that the first and second disks are on rod $$$B$$$, the third disk on rod $$$C$$$ and the fourth on rod $$$A$$$. The table below shows all the $$$7$$$ moves necessary to solve the Tower of Hanoi puzzle with three disks. $$$$$$ \begin{array}{|c|c|} \hline \text{Move No} & \text{Distribution of disks among the rods} \cr \hline 0 & AAA \cr \hline 1 & BAA \cr \hline 2 & BCA \cr \hline 3 & CCA \cr \hline 4 & CCB \cr \hline 5 & ACB \cr \hline 6 & ABB \cr \hline 7 & BBB \cr \hline \end{array} $$$$$$ Write a program that will identify the number of the team with the maximum amount of moves in the Tower of Hanoi. If there are several such teams, determine the number of the first one.

The first line contains two integers: $$$N$$$ – the number of disks and $$$M$$$ – the number of teams that solved the puzzle. The next $$$M$$$ lines contain $$$N$$$ symbols. Line $$$i$$$ contains the result of team $$$i$$$. Each line represents the distribution of disks among rods $$$A$$$, $$$B$$$, and $$$C$$$ after performing move $$$K$$$ $$$(0 \leq K \leq 2^N-1)$$$. All teams use the standard classical algorithm of moving with the maximum of $$$2^N-1$$$ moves. The number of disks $$$N$$$ satisfies the condition $$$1 \leq N \leq 10^3$$$. Number of teams: $$$1 \leq M \leq 10^3.$$$

A single positive integer – the number of the team with the maximum amount of moves. If there are several such teams, the team with minimum number of them is displayed.

4 7
CAAA
AAAA
CCCB
CBAA
BBAA
BBCA
CCCA

3

3 4
AAA
BBB
BAA
BBB

2