문제

수열 $X$에서 원소 몇 개를 골라 원래의 순서를 유지한 채 이어 붙여 만든 수열을 $X$의 부분 수열이라고 한다. 예를 들어 문자열 ACAYKP의 부분 수열로는 AAK, CYP, ACAYKP 등이 있고, KAY는 부분 수열이 아니다.

알파벳 대문자로 이루어진 두 문자열 $A$와 $B$가 주어진다. $A$의 부분 수열이면서 동시에 $B$의 부분 수열인 문자열을 두 문자열의 공통 부분 수열이라고 하며, 그중 가장 긴 것을 최장 공통 부분 수열(LCS, Longest Common Subsequence)이라고 한다.

두 문자열 $A$와 $B$가 주어졌을 때, 최장 공통 부분 수열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 $A$가, 둘째 줄에 문자열 $B$가 주어진다. 두 문자열은 모두 알파벳 대문자로 이루어져 있으며, 길이는 각각 $1$ 이상 $1\,000$ 이하이다.

출력

첫째 줄에 두 문자열의 최장 공통 부분 수열을 하나 출력한다. 최장 공통 부분 수열의 길이가 $0$이라면 빈 줄을 출력한다. 정답이 여러 개라면 그중 하나만 출력한다.

예제 입력 1

ACAYKP
CAPCAK

예제 출력 1

ACAK

예제 입력 2

ABCBDAB
BDCAB

예제 출력 2

BCAB

예제 입력 3

ABC
DEF

예제 출력 3