题目描述

在刚才的课堂上，小程研究了最长公共子序列问题，使用了动态规划求解了LCS的长度，现在除了长度之外他还想求出LCS的具体序列值。

输入格式

第一行一个长度在10000以内小写字母组成的字符串X。 第二行一个长度在10000以内小写字母组成的字符串Y。

输出格式

第一行，一个整数，表示X和Y的最长公共子序列长度。 第二行，一个字符串，表示X和Y的最长公共子序列的具体序列值。如果LCS的长度为0，第二行则不需要输出。 本题使用特殊判题，如果有多个LCS输出一种即可。

abcd
dabec

3
abc

数据规模与约定

对于 $100\%$ 的数据，$0 \le n \le 10^7$。