Longest Common Subsequence in DNA Strings

You are given two DNA strings consisting only of the characters A, C, G, and T. Your task is to compute the Longest Common Subsequence (LCS) between these two strings.

The LCS of two strings is defined as the longest sequence that appears in both strings (not necessarily consecutively). The problem can be formulated using Dynamic Programming. The recurrence relation is given by:

\(dp(i,j)=\begin{cases}0 & \text{if } i=0 \text{ or } j=0,\\ dp(i-1,j-1)+1 & \text{if } s_1[i]=s_2[j],\\ \max(dp(i-1,j),dp(i,j-1)) & \text{otherwise.} \end{cases}\)

Implement a program that reads two DNA sequences from stdin and outputs their LCS to stdout. If there is more than one valid answer, output the one computed by the standard dynamic programming algorithm described below.

inputFormat

The input consists of exactly two lines. Each line contains a DNA sequence consisting of uppercase letters A, C, G, and T. Both sequences are non-empty and may have lengths up to 1000 characters.

outputFormat

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

## sample

AGGTAB
GXTXAYB

GTAB

</p>