편집 거리 삼각형

두 문자열 $S$와 $T$ 사이의 편집 거리는 다음의 연산들을 사용하여 $S$에서 $T$로 바꾸기 위한 최소 연산 횟수로 정의한다.

• 하나의 문자를 임의의 위치에 추가한다.
• 하나의 문자를 제거한다.
• 하나의 문자를 다른 문자로 바꾼다.

알파벳 대문자로만 이루어진 문자열 $S$와 $T$가 주어진다. 역시 알파벳 대문자로만 이루어진 길이 $1$ 이상의 문자열 $U$ 중에서 다음 조건을 충족하는 문자열이 존재한다면, 그러한 문자열을 아무거나 하나 찾아보자.

• $S$와 $U$ 사이의 편집 거리는 정확히 $1$이고, $T$와 $U$ 사이의 편집 거리도 정확히 $1$이다.

첫째 줄에 문자열 $S$의 길이 $n$과 문자열 $T$의 길이 $m$이 공백으로 구분되어 주어진다. ($1\le n,m\le 5\, 000$)

둘째 줄에 알파벳 대문자로 이루어진 문자열 $S$가 주어진다.

셋째 줄에 알파벳 대문자로 이루어진 문자열 $T$가 주어진다.

문제의 조건을 충족하는 길이 $1$ 이상의 문자열 $U$가 존재한다면, 첫째 줄에 1을 출력하고, 둘째 줄에 $U$를 출력한다. 그러한 $U$가 여러 가지라면 아무거나 하나를 출력한다.

존재하지 않는다면 첫째 줄에 0을 출력한다.