AT_maximum_cup_2023_d 編集ゲーム

正整数 $ K $ と $ 4 $ 種類の英大文字 `ATGC` のみからなる文字列 $ S $ が与えられます。 S君とU君がS君から始めて交互に次の操作を行います。 - 後述の条件を満たしながら以下の $ 3 $ 種類の操作のうち $ 1 $ つを選んで実行する。 - $ S $ のある $ 1 $ 文字を `ATGC` のどれか $ 1 $ 文字に置換する。 - $ S $ のある位置(先頭・末尾でもよい)に`ATGC` のどれか $ 1 $ 文字を挿入する。 - $ S $ のある $ 1 $ 文字を削除する(この操作は $ S $ が非空の時にのみ行える)。 - 条件：操作前の文字列を $ X $ 、操作後の文字列を $ Y $ とした時、以下の $ 2 $ つの条件を満たす - $ Y $ の文字列長は $ K $ 以下 - $ Y $ は $ X $ より辞書順で真に大きい 先に操作が出来なくなった方が負け、もう一方の人が勝ちとなります。 S君とU君が最善を尽くした場合、どちらが勝つかを判定してください。

入力は以下の形式で標準入力から与えられる。 > $ K $ $ S $

S君が勝つ場合は `S` と、U君が勝つ場合は `U` と出力せよ。

### Constraints - $ 1 \leq K \leq 10^9 $ - $ 1 \leq |S| \leq \min(3 \times 10^5, K) $ - $ K $ は整数 - $ S $ は `ATGC` のみからなる文字列