如果字符串 $s$ 存在字符串 $w, v, u$（可能为空），使得 $s = wxvyu$，则称字符串对 $(x, y)$ 为字符串 $s$ 的一个子对（subpair）。字符串 $x$ 和 $y$ 也可以为空。

如果字符串对 $(x, y)$ 同时是字符串 $s_1$ 和 $s_2$ 的子对，则称其为 $s_1$ 和 $s_2$ 的公共子对。

子对 $(x, y)$ 的长度定义为 $|x| + |y|$，即 $x$ 和 $y$ 的长度之和。

给定两个由小写拉丁字母组成的字符串 $s_1$ 和 $s_2$，请找出它们长度最大的公共子对。

输入格式

第一行包含字符串 $s_1$。 第二行包含字符串 $s_2$。

两个字符串均为非空，由小写拉丁字母组成，且长度均不超过 $2 \cdot 10^5$。

输出格式

输出的第一行和第二行应分别包含所选子对中的第一个字符串和第二个字符串。这两个字符串均可以为空。如果存在多个长度最大的公共子对，输出其中任意一个即可。

样例

样例输入 1

abacaba
cabina

样例输出 1

cab
a

样例输入 2

abba
acdc

样例输出 2

a

样例输入 3

empty
ans

样例输出 3

说明

在第一个测试样例中，长度最大的公共子对是 (“cab”, “a”)。

在第二个测试样例中，存在两个长度最大的公共子对：(“”, “a”) 和 (“a”, “”)。

在第三个测试样例中，两个字符串不包含任何公共子串，因此最大长度为 0，答案包含两个空字符串。