BerTV 上有一款新的电视游戏。在这个游戏中,两个玩家得到一个由 2n 位数字组成的数字 A。在每个回合之前,玩家决定谁将采取下一步行动。每个玩家应该精确地进行 n 步。轮到第 i 个玩家时,取出 A 最左边的数字并将其附加到他或她的数字 Si 上。之后,最左边的数字将从 A 中删除。最初,两个玩家(S1 和 S2)的号码都是“空”。数字 A、S1、S2 中允许有前导零。游戏结束时,第一个玩家获得 S1 美元,第二个玩家获得 S2 美元。
有一天,荷马和玛吉来玩游戏。他们事先设法知道了数字A。他们想要找到这样的移动顺序,使得他们两人都恰好进行了 n 步,并且最大化了他们的总奖金。帮助他们。
输入
第一行包含整数 n (1 ≤ n ≤ 18)。第二行包含恰好由 2n 位数字组成的整数 A。该数字可以有前导零。
输出
输出 2n 个字符“H”和“M”的行——Homer 和 Marge 的移动序列,这给了他们最大可能的总奖金。每个玩家必须精确地进行 n 步。如果有多个解,输出任意一个。
示例
输入 #1
2 1234
输出 #1
HHMM
输入 #2
2 9911
输出 #2
HMHM