You are given two strings $$$S$$$ and $$$T$$$. Find out one of the Longest Common Subsequences of the two given strings.
A subsequence is a sequence derived from another sequence by deleting some or no elements, while maintaining the original order of the remaining elements.
A common subsequence is a subsequence that appears in both strings.
The first line contains string $$$S$$$ ($$$1 \le |S| \le 3000$$$).
The second line contains string $$$T$$$ ($$$1 \le |T| \le 3000$$$).
$$$S$$$ and $$$T$$$ consist of lower case English letters.
Output a single string representing the Longest Common Subsequence of the two given strings. Multiple LCS answers can exist. You can print any one of them, or -1 if no common subsequence is found.
Input:
algopath pathalzguo
Output:
path
For the strings algopath and pathalzguo, the longest common subsequence has a length of 4.
One possible answer is path:
Another possible answer is algo:
Since multiple answers exist, either path or algo will be accepted as a correct output.