作为一名著名的细菌和蛋白质收集者，你正在领导一项关于细菌和病毒蛋白质传播的研究。作为这项研究的一部分，全球各地的公共场所都已采集了 DNA 样本。

实验室刚刚送回了测序后的 DNA 样本，你现在想要证明你的假设：尽管这些样本采集自不同的大洲，但它们仍然是相关的。然而，事实证明它们并不相关。实际上，这些样本是包含字符 “ACGT” 的独立均匀随机 DNA 序列。这意味着序列中的每个字符都有恰好 25% 的概率为 ‘A’、‘C’、‘G’ 或 ‘T’ 中的任意一个。

尽管如此，你仍然希望说服你的同事这些样本是相关的。你决定，当两段 DNA 共享至少一半的代码时，它们就是相关的：如果两个序列的长度均为 $n$，当它们共享一个长度至少为 $\frac{1}{2}n$ 的公共子序列$^2$时，它们就是相关的。

给定两个独立的均匀随机 DNA 序列 $A$ 和 $B$，你的任务是找到一个公共子序列来证明它们是相关的。你已经做了一些分析，并确认在 $n = 10^6$ 的情况下，每个实例的失败概率实际上小于 $10^{-1000}$。

一些可能相关的 DNA 片段

输入格式

输入包含：

• 一行，包含一个整数 $n$，表示 DNA 序列的长度。
• 一行，包含一个字符串 $A$，由 $n$ 个 “ACGT” 中的独立均匀随机字符组成。
• 一行，包含一个字符串 $B$，由 $n$ 个 “ACGT” 中的独立均匀随机字符组成。

你的提交将在 100 个测试用例上运行，所有用例均满足 $n = 10^6$。样例较小，仅供说明。

你的每次提交都将在新的随机测试用例上运行。

提供了一个测试工具用于在大型随机输入上运行你的提交。它不会验证你答案的正确性。

$^2$ 当序列 $S$ 可以通过删除序列 $A$ 中的部分或全部元素（同时保持剩余元素的顺序）得到时，称 $S$ 为 $A$ 的子序列。

输出格式

输出一个长度至少为 $\frac{1}{2}n$ 的公共子序列。

如果存在多个有效的解决方案，你可以输出其中任意一个。

样例

样例输入 1

20
TCCGATCGCTCTAGAACTAG
CTCACTAGCTCTTCGCCGAC

样例输出 1

TCATGCTCTGCG

样例输入 2

20
AGGCTTGAACGATAGACAAC
AGCTAAAGCTAGCTAGACTT

样例输出 2

AGCTAACATAGAC