题目背景

翻译自 CSES-1087 题。

题目描述

给定一个由字符 $A、C、G$ 和 $T$ 组成的 $DNA$ 序列。

你的任务是找到一个最短的 $DNA$ 序列，它不是原始序列的子序列。

输入格式

输入的唯一一行包含一个长度为 $n$ 的 $DNA$ 序列。

输出格式

输出一个最短的 $DNA$ 序列，它不是原始序列的子序列。如果有多个解，你可以输出任意一个。

样例

ACGTACGT

AAA

说明/提示

$1 \leq n \leq 10^6$。