题目描述

题目译自 XXVI Olimpiada Informatyczna – I etap Niedbałość

Bajtazar 先生是 Bajtocji 第 $2^{8}-1$ 高中的生物老师。他给 Bajtek 和同学们布置了一道遗传学作业：找出两个基因型之间的最大亲缘关系。也就是说，你得找到这两个基因型中都包含的最长氨基酸序列（不一定连续）。Bajtek 他们很清楚，这任务烦琐得要命，更别提懒惰的 Bajtazar 先生居然会花时间检查。他们从学长那儿听说，这位老师检查作业很马虎——他只看你给的序列能不能在某处再加一个氨基酸，还保持是两个基因型的子序列。如果加不进去，你就能拿满分。

假设基因型是只由字母 $\texttt{A}$、$\texttt{C}$、$\texttt{G}$、$\texttt{T}$ 组成的序列。设 $S = (s_{1}, \ldots, s_{n})$ 和 $T = (t_{1}, \ldots, t_{m})$ 是给定的两个基因型，长度分别为 $n$ 和 $m$。要拿满分，你需要给出一个序列 $W = (w_{1}, \ldots, w_{k})$，它既是 $S$ 的子序列，也是 $T$ 的子序列，而且不存在任何长度为 $k+1$ 的序列 $W^{\prime}$，包含 $W$ 作为子序列，同时还是 $S$ 和 $T$ 的子序列。

请你帮 Bajtek 和他的小伙伴们拿到最高分。

输入格式

输入第一行是一个长度为 $n$ 的基因型，用大写字母 $\texttt{A}$、$\texttt{T}$、$\texttt{C}$、$\texttt{G}$ 表示。

第二行是另一个长度为 $m$ 的基因型，格式相同。

输出格式

输出一行，用 $\texttt{A}$、$\texttt{C}$、$\texttt{G}$、$\texttt{T}$ 字母组成一个不可扩展的序列，作为输入中两个基因型的亲缘证据。如果有多个正确答案，你的程序可以输出任意一个。

保证答案始终存在且非空。

ACTAGG
GATCA

ACA

ATA 和 G 也是合法的输出。

附加样例

1. $n=m=7$，基因型只有字母 $\texttt{A}$ 和 $\texttt{T}$；
2. $n=100, m=10000$，第一个基因型是第二个的子序列；
3. $n=m=1000000$，第一个基因型的氨基酸按字母顺序排列。

数据范围与提示

详细子任务附加限制及分值如下表所示。