← 返回题目列表

AtCoder · maximum_cup_2023_d

D. 编辑游戏

中文机器翻译题面 查看原题

配点 : 100 点

問題文

正整数 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 组成的字符串

入力

输入将以以下格式从标准输入给出。

K
S

出力

如果S获胜 S 如果U赢了, U 。


入力例 1

3
AC

出力例 1

S

入力例 2

1
T

出力例 2

U

入力例 3

1200
AGC

出力例 3

S