A7960 | TV Game

There is a new TV game on BerTV. In this game two players get a number $A$ consisting of $2n$ digits. Before each turn players determine who will make the next move. Each player should make exactly $n$ moves. On it's turn $i$ -th player takes the leftmost digit of $A$ and appends it to his or her number $S_{i}$ . After that this leftmost digit is erased from $A$ . Initially the numbers of both players ( $S_{1}$ and $S_{2}$ ) are «empty». Leading zeroes in numbers $A,S_{1},S_{2}$ are allowed. In the end of the game the first player gets $S_{1}$ dollars, and the second gets $S_{2}$ dollars.

One day Homer and Marge came to play the game. They managed to know the number $A$ beforehand. They want to find such sequence of their moves that both of them makes exactly $n$ moves and which maximizes their total prize. Help them.

The first line contains integer $n$ ( $1<=n<=18$ ). The second line contains integer $A$ consisting of exactly $2n$ digits. This number can have leading zeroes.

Output the line of $2n$ characters «H» and «M» — the sequence of moves of Homer and Marge, which gives them maximum possible total prize. Each player must make exactly $n$ moves. If there are several solutions, output any of them.