# TLE?
<>;
$_=<>;
/U(.(?1).|M)G(?{$%++})^/;
print$%