問題文

正整数 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君が最善を尽くした場合、どちらが勝つかを判定してください。

制約

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

入力例 1

3
AC

出力例 1

S

入力例 2

1
T

出力例 2

U

入力例 3

1200
AGC

出力例 3

S