配点 : 100 点
問題文
正整数 K 和 4 大写字母的类型
仅由 ATGC 组成的字符串 S 被给予。
S先生和U先生将从S先生开始依次执行以下操作。
-
以下同时满足下述条件。 3 操作类型 1 选择一项并执行。
- S 有 1 字符
ATGC任何一个 1 替换为字符。 - S 在某个位置(开始或结束都可以)
ATGC任何一个 1 插入字符。 - S 有 1 删除字符(此操作 (仅当 S 非空时才能完成)。
- S 有 1 字符
-
条件:操作前的字符串 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