Longest Common Subsequence

Given two strings, your task is to compute 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). This problem can be solved efficiently using dynamic programming. Formally, if the two strings are \(S_1\) and \(S_2\) with lengths \(m\) and \(n\) respectively, you are to compute the sequence \(LCS\) such that its length is maximized and for each character \(LCS[i]\), there exist indices \(j\) in \(S_1\) and \(k\) in \(S_2\) with \(j < j'\) and \(k < k'\) for consecutive characters in the subsequence.

Note: The input is guaranteed to be two strings. If needed, use the dynamic programming recurrence:

\[ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } S_1[i-1] = S_2[j-1] \ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases} \]

inputFormat

The input is read from standard input (stdin) and consists of two lines. The first line contains the first string and the second line contains the second string.

outputFormat

The output is written to standard output (stdout) and is a single line containing the longest common subsequence of the two given strings. If there is no common subsequence, output an empty string.

## sample

AGGTAB
GXTXAYB

GTAB