Distinct Common Subsequences

Given two sequences (X=x_1x_2\ldots x_m) and (Y=y_1y_2\ldots y_n), find all distinct common subsequences that are subsequences of both (X) and (Y). A sequence (Z=z_1z_2\ldots z_k) is a subsequence of (X) if there exists a strictly increasing sequence of indices (i_1,i_2,\ldots,i_k) such that (z_j=x_{i_j}) for (1\le j\le k).

Output the common subsequences in lexicographical order (according to standard string order), each on a new line. Note that the empty sequence (an empty line) is also considered a valid common subsequence.

inputFormat

The input consists of two lines. The first line contains the sequence (X), and the second line contains the sequence (Y). Both sequences are non-empty and their lengths are small (for instance, at most 15 characters).

outputFormat

Output all distinct common subsequences of (X) and (Y) in lexicographical order, each printed on a new line. The empty subsequence should be printed as an empty line.

sample

AB
AB

A
AB
B