Longest Common Subsequence

Given two strings, find their Longest Common Subsequence (LCS). The LCS of two strings is the longest sequence that appears in both strings in the same order. Note that the characters do not need to be contiguous.

For example, given the strings "ABCBDAB" and "BDCAB", one valid LCS is "BCAB".

inputFormat

The input consists of exactly two lines. The first line contains the first string and the second line contains the second string. Both strings consist of uppercase English letters.

outputFormat

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

ABCBDAB
BDCAB

BCAB