题目描述

给定字符串 $s$ 和 $t$。找到最长的字符串，它是 $s$ 和 $t$ 的子序列。

说明

一个字符串 $x$ 的 子序列 是通过从 $x$ 中删除零个或多个字符并将剩余的字符拼接在一起而得到的，但不改变它们的顺序。

约束条件

• $s$ 和 $t$ 是由小写英文字母组成的字符串。
• $1 \leq |s|, |t| \leq 3000$

输入

输入将从标准输入读取，并具有以下格式：

$s$ $t$

输出

打印一个最长的字符串，它是 $s$ 和 $t$ 的子序列。如果存在多个这样的字符串，则可以接受任意一个。

示例输入1

axyb
abyxb

示例输出1

axb

答案可以是 axb 或 ayb；任何一个都可以接受。

示例输入2

aa
xayaz

示例输出2

aa

示例输入3

a
z

示例输出3

答案为空字符串。

示例输入4

abracadabra
avadakedavra

示例输出4

aaadara