Problem H
Fullkomin mylla

Fullkomin mylla

Arnar and Hannes are very competitive friends and love competing with one another. They are always looking for new games to compete at and they both prefer games involving a lot of thinking.

Hannes found a new version of tic-tac-toe called Fullkomin mylla and found it likely he’d beat Arnar at this game. He thus went to Arnar and asked him whether he was up for it. Arnar said he’d be up for it but only if the loser paid for the food next time they went to American Style.

To be sure that the better player won, and that luck wouldn’t be involved, they decided to play a few rounds, and the first player to win $n$ rounds would win the bet. Each round will consist of $5$ games of Fullkomin Mylla and whoever wins more games out of the $5$, wins that round.

Furthermore they aren’t going to spend time on unneccesary games. Thus they will stop a round as soon as its victor is clear. For example if Arnar wins the first three games of a round they won’t play more games in this round, since Arnar will win the round no matter what the results of the last two games are.

Rules

Fullkomin mylla is played by creating one large tic-tac-toe board and then in each cell of the large board there is a smaller tic-tac-toe board. Players take alternating turns and choose cells in the small boards to play in until a victor emerges. If a player wins one of the small boards, the corresponding cell in the large board is filled in with that players mark. If a player wins the large board, they win the game.

Player $1$ starts and can choose any cell in the large board to play in and then chooses a cell in the smaller board contained in that cell. After that player $2$ has to play in the smaller board that corresponds to the cell in the small board that player $1$ chose. If that board is already won then player $2$ can choose any cell. This repeats until one player wins the game or there are no moves left to make and the game’s a tie.

Input

The first line of the input contains an integer $N$ which is the number of rounds needed to win the bet. The next line contains a string $S$ describing who won each game, A if Arnar won and H if Hannes won. You may assime that no ties came up and that the string describes exactly the games that were played, in the order they were played.

Output

Print who lost the bet.

Explanation of Sample Input

In the first sample the winner is the first player to win $2$ rounds. The games proceeded as follows:

1. The first round begins. Arnar wins the first game of this round.

2. Hannes wins the second game.

3. Arnar wins the third game. The score is now 2-1 for Arnar, but Hannes could still win the round, so they continue.

4. Hannes wins the fourth game.

5. Arnar wins the fifth game, so Arnar wins the first round 3-2.

6. The second round begins. Arnar wins the first game.

7. Arnar also wins the second game.

8. Hannes now comes in hot and wins the third game.

9. Hannes wins the fourth game.

10. Hannes is on a roll and wins the fifth game, so he wins the second round 3-2. Now both have won 1 round.

11. The third round begins. Hannes wins the first game.

12. Arnar wins the second game.

13. Hannes wins the third game.

14. Arnar wins the fourth game.

15. Arnar wins the fifth game and thus wins the round 3-2. Now Arnar has won two rounds and is thus victorious!

In the second sample the winner is the first player to win $2$ rounds. The games proceeded as follows:

1. The first round begins. Hannes wins the first game.

2. Hannes wins the second game.

3. Hannes is on a wild roll and also wins the third games. Now Hannes has three wins, but there are only games left in the round. Thus Arnar has no chance of winning this round, so the round ends 3-0 for Hannes.

4. The second round starts. Arnar wins the first ggame and thus wins back some respect after being steamrolled by Hannes in the first round.

5. Hannes doesn’t let this affect him and wins the second game.

6. Hannes then just keeps going and wins the third game.

7. He shoots and he scores! Hannes wins the fourth game. He has three wins this round and Arnar only one. There is only one game left and no matter how it goes Hannes will win it. Thus they stop this round and Hannes wins 3-1. Hannes has now won two rounds and thus wins the bet.

Scoring

The solution will be tested on input data of varying difficulty and the data is divided into groups as shown in the table below. The solution will then be scored according to how many groups are solved.

2
AHAHAAAHHHHAHAA

Hannes

2
HHHAHHH

Arnar