여행

앨리스와 밥이 함께 여행을 떠나려 한다. 두 사람은 각자 방문할 도시들을 정해진 순서대로 나열한 경로를 하나씩 준비했다. 하나의 경로에서 같은 도시를 여러 번 방문할 수도 있다.

함께 여행하려면 두 사람은 하나의 공통 경로에 합의해야 한다. 누구도 자기 경로에 있는 도시들의 순서를 바꾸거나 새로운 도시를 추가하고 싶어 하지 않으므로, 할 수 있는 일은 일부 도시를 지우는 것뿐이다. 당연히 공통 경로는 가능한 한 길어야 한다.

이 지역에는 정확히 26개의 도시가 있으며, 각 도시는 소문자 a부터 z까지의 알파벳으로 표현된다. 따라서 공통 경로란 두 목록의 최장 공통 부분 수열(LCS)을 뜻한다.

첫째 줄에는 앨리스의 목록이, 둘째 줄에는 밥의 목록이 주어진다. 각 목록은 공백 없이 이어진 길이 1 이상 80 이하의 소문자 a~z 문자열이다.

가장 긴 공통 경로를 모두, 한 줄에 하나씩 출력한다. 같은 경로를 두 번 출력해서는 안 된다. 경로들은 사전순(오름차순)으로 정렬하여 출력한다. 비어 있지 않은 공통 경로가 적어도 하나 존재하며, 서로 다른 경로는 최대 1000개임이 보장된다.