Background

Special for beginners, ^_^

Description

一个给定序列的子序列是在该序列中删去若干元素（也可以不删去）后得到的序列。例如Z="BCDB" 就是X＝"ABCBDAB"的一个子序列，而Z="CBBD"则不是X的子序列。 给定三个序列 X，Y和Z，如果Z既是X的一个子序列又是Y的一个子串，则称Z是X和Y的公共子序列。

例如X＝"ABCBDAB"，Y＝BDCABA"，则序列"BCA"即为X和Y的一个公共子序列，但不是X和Y的最长公共子序列(LCS)，因为还有比它更长的公共子序列"BCBA"。事实上"BCBA"是X和Y的一个LCS ，"BDAB"也是一个LCS。 现输入两个序列X和Y，要求出X和Y的最长公共子序列。

Format

Input

第1行：两个用字符串表示的序列X和Y。$1 \leq X.size(), Y.size() \leq 1000$两个序列之间用1个空格分隔。序列均由大写字母组成。

Output

第1行：一个整数L，表示两个序列的最长公共子序列的长度。

第2行：一个字符串S，表示两个序列的最长公共子序列。如果存在多个长度等于L的子序列，输出在X序列中位置最靠前的一个。

Samples

ABCBDAB
BDCABA

4
BCBA

Limitation

1s, 1024KiB for each test case.