이름 짓기

새끼 고양이, Kirgiz03 제공, Pixabay

부모가 되는 것은 참으로 힘들 수 있다. 아이들은 끊임없이 칭얼대고, 지긋지긋하게 보채기까지 한다. 그래서 두 아이의 부모인 당신은 아이들을 진정시키기 위해 새끼 고양이를 사기로 했다. 하지만 의견 충돌이 생겼다. 아이들은 새끼 고양이의 이름을 무엇으로 할지 합의하지 못했다. 두 아이는 저마다 원하는 이름을 골랐지만, 최종 결정권은 당연히 당신에게 있다. 아이들이 고른 두 이름이 모두 새끼 고양이 이름의 부분 수열이면 충분하다는 것을 당신은 알고 있다. 당신은 자신의 편의를 위해 이름을 가능한 한 짧게 짓고 싶다.

문자열 $s$에서 문자를 제거하여 $t$만 남길 수 있을 때, 문자열 $t$는 문자열 $s$의 부분 수열이다. 예를 들어 문자열 snati은 문자열 í**s**k**n****a**t**t**le**i**kur의 부분 수열이다.

점수 배점

그룹 | 점수 | 제한

1 | 33 | $n \leq 10$, 문자열에는 문자 a와 b만 포함된다

2 | 27 | $n \leq 10$

3 | 40 | $n \leq 10^3$

입력은 두 줄로 주어진다. 각 줄에는 두 아이가 각각 새끼 고양이에게 붙이고 싶어 하는 이름을 나타내는 문자열이 주어진다. 각 문자열은 적어도 한 글자이고 최대 $n$글자이며, 영어 소문자로만 이루어진다.

두 아이가 모두 받아들일 수 있는 새끼 고양이의 이름을 출력한다. 선택할 수 있는 모든 이름 가운데 가장 짧은 것을 선택해야 한다. 가능한 이름이 하나보다 많다면 그중 어느 것이든 출력해도 된다.