Common Subsequences

Given two strings s₁ and s₂, your task is to find all common subsequences between them. A subsequence of a string is a new string generated from the original string by deleting some (or no) characters without changing the order of the remaining characters.

The common subsequences should be output in descending order according to their lengths. If two subsequences have the same length, they should be sorted in lexicographical order.

Note: If there are no common subsequences, output nothing.

Mathematical Note: A subsequence of a string \(s\) is defined as a sequence \(s_{i_1}, s_{i_2}, \dots, s_{i_k}\) where \(1 \leq i_1 < i_2 < \dots < i_k \leq |s|\).

inputFormat

The input consists of two lines. The first line contains the string s₁ and the second line contains the string s₂. The strings may include letters, digits, or special characters.

outputFormat

Output all the common subsequences, each on a separate line, following the order: first by descending length, then lexicographically for subsequences of the same length. If there are no common subsequences, output nothing.

## sample

abc
abc

abc
ab
ac
bc
a
b
c

</p>