13446번 - 새로운 가게 이름

강호와 준규가 기존에 하던 가게를 정리하고 힘을 합쳐서 새로운 가게를 열었다.

오늘은 새로운 가게의 이름을 정하려고 한다. 두 사람은 예전에 사용하던 가게 간판을 가지고 있고, 이 간판을 이용해서 새로운 가게의 이름을 만들려고 한다. 새로운 가게의 이름을 만드는 과정은 다음과 같다. 이때, 대소문자는 구분한다.

• 강호의 간판에서 두 조각을 잘라낸다. 각 조각은 비어있지 않은 연속 부분 문자열이어야 한다. 예를 들어, 간판에 "abCDeF"가 쓰여 있을 때, "bC", "e"로 조각 잘라내거나, "CDeF", "ab"로 잘라내는 것은 가능하다. 하지만, "aC"와 "eF"는 "aC"가 연속되지 않았기 때문에 불가능하고, "abCD"와 ""는 빈 문자열을 포함해서, "DeF"와 "CD"는 조각을 만들 수 없는 경우이기 때문에 불가능하다. 이렇게 강호의 간판에서 잘라낸 문자열을 A와 B라고 한다.
• 준규의 간판에서도 두 조각을 잘라내며, 강호의 규칙과 동일하게 잘라낸다. 준규의 간판에서 잘라낸 문자열은 C와 D라고 한다.
• 이때, A + C와 B + D는 같아야 하며, 이것이 새로운 가게의 이름이 된다. 여기서 +는 문자열의 연속을 의미한다.

강호의 간판에 쓰여 있는 문자열 X와 준규의 간판에 쓰여 있는 문자열 Y가 주어졌을 때, 가능한 새로운 가게의 이름 중에서 가장 긴 것을 구하는 프로그램을 작성하시오. 만약, 길이가 긴 것이 여러 가지라면 사전 순으로 앞서는 것을 출력한다.

첫째 줄에 강호의 문자열 X과 준규의 문자열 Y가 주어진다. 문자열의 길이는 47을 넘지 않으며, 알파벳 대/소문자로만 이루어져 있다.

가능한 새로운 가게의 이름 중에서 가장 긴 것을 출력한다. 만약, 길이가 긴 것이 여러 가지라면 사전 순으로 앞서는 것을 출력한다.

만약, 가능한 가게의 이름이 없으면 -1을 출력한다.