Problem3404--TV Game

3404: TV Game

[Creator : ]
Time Limit : 2.000 sec  Memory Limit : 256 MiB

SubmitSolved: 0Submit Num: 0StatisticsShowOff!

Description

time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 Si. After that this leftmost digit is erased from A. Initially the numbers of both players (S1 and S2) are «empty». Leading zeroes in numbers A,S1,S2 are allowed. In the end of the game the first player gets S1 dollars, and the second gets S2 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.

Input

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

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.

Examples
Input
2
1234
Output
HHMM
Input
2
9911
Output
HMHM

Source/Category

 
Submit