AT_maximum_cup_2023_d 編集ゲーム

给定一个正整数 $K$ 和一个仅由四种大写英文字母 `ATGC` 构成的字符串 $S$。 S 君和 U 君轮流操作，S 君先手。每次可交替执行下列 3 种操作之一，且需满足后文条件： - 从以下三种操作中任选一个进行： - 将 $S$ 中的某个字符替换为 `ATGC` 的某个字符； - 在 $S$ 的任意位置（包括开头或结尾）插入一个 `ATGC` 字符； - 删除 $S$ 中的某个字符（仅当 $S$ 非空时可以进行）。 - 条件：操作前的字符串为 $X$，操作后的为 $Y$，须同时满足： - $Y$ 的长度不超过 $K$； - $Y$ 的字典序严格大于 $X$。 无法进行操作者判负，另一方获胜。 若 S 君和 U 君都采取最优策略，判断谁能获胜。

输入从标准输入获得，格式如下： > $K$ $S$

若 S 君获胜输出 `S`，若 U 君获胜输出 `U`，不带引号。

### 限制条件 - $1 \leq K \leq 10^9$ - $1 \leq |S| \leq \min(3 \times 10^5, K)$ - $K$ 为整数 - $S$ 仅由 `ATGC` 字符组成 由 ChatGPT 5 翻译