Byteotian 高中 $2^8 - 1$ 班的科学老师 Byteasar 先生非常不公平。他给 Bytie 和他的朋友们布置了以下遗传学任务：确定两个基因型的相似度。为此，学生们必须找到两个基因型的最长公共子序列（不一定连续）。学生们非常清楚这是一项繁琐的任务，根本不相信以懒惰著称的 Byteasar 先生会认真检查。在询问了高年级同学后，他们几乎可以肯定，老师只会检查学生找到的序列是否可以通过在任意位置插入单个氨基酸来扩展，使得扩展后的序列仍然是两个基因型的公共子序列。如果无法进行这样的插入，老师就会给该解法打最高分。

我们假设基因型是由字母 A、C、G 和 T 组成的序列。设 $S = (s_1, \dots, s_n)$ 和 $T = (t_1, \dots, t_m)$ 分别表示长度为 $n$ 和 $m$ 的两个基因型。如果 $W = (w_1, \dots, w_k)$ 是 $S$ 和 $T$ 的公共子序列，且对于任何包含 $W$ 作为子序列的序列 $W'$，若 $W'$ 不是 $S$ 和 $T$ 的公共子序列，则称 $W$ 为作业的最高分答案。

请帮助 Bytie 和他的朋友们在道德灰色地带中取得最高分。

输入格式

标准输入的第一行包含第一个基因型，表示为一个由 $n$ 个大写字母 A、T、C 和 G 组成的字符串。第二行包含另一个基因型，长度为 $m$，表示方式相同。

输出格式

在标准输出的第一行，输出一个字符串。它应由字母 A、C、G 和 T 组成，代表输入序列的一个不可扩展的公共子序列。如果存在多个正确答案，你的程序可以输出其中任意一个。

你可以假设存在非空的公共子序列。

样例

输入格式 1

ACTAGG
GATCA

输出格式 1

ACA

说明

或者输出：

ATA

或者：

G

评分标准

测试集包含以下子任务。每个子任务内可能包含多个测试点。