1183 - 最长公共子序列

通过次数

0

提交次数

0

Time Limit : 1 秒
Memory Limit : 128 MB

 若给定序列X={x1,x2,,xm},则另一序列Z={z1,z2,,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,,ik}使得对于所有j=1,2,,k有:zj=xij。例如,序列Z={BCDB}是序列X={ABCBDAB}的子序列,相应的递增下标序列为{2357}

给定2个序列XY,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列XY的公共子序列。

给定2个序列X={x1,x2,,xm}Y={y1,y2,,yn},找出XY的最长公共子序列。

Input

为保障统计正确,需在输入字符数组x和y的第一个字符设置标示,该字符不参与统计

第一行输入序列x。

第二行输入序列y。

Output

第一行输出最大子串长度。

第二行输出最大子串。

Examples

Input

@thiscbook
#tisnook

Output

6
tisook