부주의한 채점

폴란드 바이토치아의 28-1 고등학교 자연과학 교사 바이타자르 선생님은 매우 불공평하다. 그는 Bajtek과 친구들에게 두 유전자형 사이의 최대 유사도를 구하는 유전학 숙제를 냈다. 학생들은 두 유전자형에 모두 부분 수열(연속일 필요는 없음)로 포함되는 가장 긴 아미노산 수열을 찾아야 한다.

선생님은 게을러서 과제를 꼼꼼히 채점하지 않는다. 그는 학생이 찾은 수열의 어느 자리에든 아미노산 하나를 끼워 넣어도 두 유전자형 모두에 여전히 부분 수열로 남는지만 확인한다. 그렇게 할 수 없으면 과제는 만점으로 인정된다.

유전자형은 A, C, G, T로 이루어진 문자열이다. $S = (s_1, \ldots, s_n)$과 $T = (t_1, \ldots, t_m)$을 각각 길이 $n$, $m$인 두 유전자형이라 하자. 학생이 수열 $W = (w_1, \ldots, w_k)$를 제출했을 때, 다음 두 조건을 만족하면 만점이다. 첫째, $W$는 $S$와 $T$의 부분 수열이다. 둘째, $W$를 부분 수열로 포함하는 길이 $k+1$의 수열 $W'$ 중에서 $S$와 $T$의 부분 수열이기도 한 것은 없다.

첫째 줄에 길이 n의 첫 번째 유전자형이 대문자 A, T, C, G로만 이루어진 문자열로 주어진다. 둘째 줄에는 같은 형식으로 길이 m의 두 번째 유전자형이 주어진다.

한 줄에 A, C, G, T로 이루어진 문자열 하나를 출력한다. 이 문자열은 두 유전자형의 공통 부분 수열이면서 더 이상 늘릴 수 없는 수열이어야 한다. 정답이 여러 개이면 그중 아무거나 출력해도 된다. 출력이 비어 있지 않다고 가정해도 된다.

$n, m \le 1000000$