Byephone

Byteman은 자신이 즐겨 쓰는 텍스트 에디터를 Byephone(단어 byte와 phone을 합쳐 지은 이름이다)이라는 새 휴대폰으로 이식하고 있다.

이 에디터의 기능 중 하나는 두 문서를 한 줄씩 비교해 주는 것으로, 이 비교는 두 문자열의 최장 공통 부분 수열(Longest Common Subsequence, LCS) 을 구하는 알고리즘에 기반한다.

그런데 Byteman은 이 휴대폰의 메모리가 그가 쓰던 알고리즘을 돌리기에는 턱없이 부족하다는 사실을 깨닫고 당신에게 도움을 청했다.

3MB의 메모리만으로, 입력으로 주어지는 두 문자열의 최장 공통 부분 수열을 구하는 프로그램을 작성하라.

첫째 줄에 두 정수 $n_1$과 $n_2$ ($1 \le n_1, n_2 \le 10\,000$)가 주어진다. 각각 두 문자열의 길이이다.

둘째 줄과 셋째 줄에는 각각 길이가 $n_1$, $n_2$인 문자열이 주어진다. 두 문자열은 모두 영어 소문자로만 이루어져 있다.

두 줄을 출력한다.

첫째 줄에는 두 문자열의 최장 공통 부분 수열의 길이 $K$를 출력한다.

둘째 줄에는 길이가 $K$인 최장 공통 부분 수열을 출력한다. 길이가 $K$인 최장 공통 부분 수열이 여러 개라면, 그중 사전순으로 가장 앞서는(가장 작은) 것을 출력한다.

공통 부분 수열이 존재하지 않으면 첫째 줄에 $0$을, 둘째 줄에는 빈 줄을 출력한다.