Longest Common Subsequence

Given two strings, find their Longest Common Subsequence (LCS). The LCS of two sequences is defined as the longest sequence that appears in both strings in the same order (not necessarily consecutively). If there are multiple LCS results, any valid answer will be accepted.

The solution should read input from stdin and output the result to stdout.

Note: The LCS is not required to be unique. For example, for the input strings "ABCBDAB" and "BDCABC", a valid output is "BCAB".

Mathematical formulation: Given two strings \(S_1\) and \(S_2\), find a string \(LCS\) such that \(LCS\) is a subsequence of both \(S_1\) and \(S_2\) and has the maximum possible length.

inputFormat

The input consists of two lines. The first line contains the first string \(S_1\) and the second line contains the second string \(S_2\). Both strings may be empty.

outputFormat

Output a single line containing the longest common subsequence of the given two strings. If there is no common subsequence, output an empty string.

## sample

ABCBDAB
BDCABC

BCAB

</p>