题目描述

Petya 记录下了两名俘虏说出的两段 Birland 语言字符串。他知道一个合法密码必须是回文串，也就是说从左向右和从右向左读完全相同。

现在需要在两段字符串中寻找一个最长公共子串，并且这个公共子串还必须是回文串。这里“子串”指连续的一段字符。

如果存在多个长度最大的答案，输出任意一个即可。

输入格式

输入包含两行，每行一个非空字符串，均只由小写英文字母 a～z 组成。

每个字符串长度不超过 $2000$。保证两个字符串至少有一个公共字符。

输出格式

输出任意一个最长的、同时出现在两个输入字符串中的回文子串。

样例 1

样例输入

abacaba
abracab

样例输出

aca

样例 2

样例输入

abbab
babbab

样例输出

abba