암호화

Boschua는 사이버 보안에 그다지 능숙하지 않다. 그는 자체 암호를 만들지 마라''라는 격언을 듣고, 하지 마라''를 무시하기로 했다.

그는 subsequences에 기반한 새로운 암호화 방식을 제안했다. 문자열 $a$을 $b$에서 문자의 상대적 순서를 유지하면서 $0$개 이상의 문자를 제거하여 얻을 수 있다면, 문자열 $a$이 문자열 $b$의 부분 수열이라고 한다. 예를 들어, hej, hejsan, jan는 모두 단어 hejsan의 부분 수열이지만, na는 그렇지 않다.

그의 암호화 방식은 다음과 같다. 문자열 $s$을 보내려면 미끼 문자열 $d$가 필요하다. $s$을 보내는 대신, $s$와 $d$를 모두 부분 수열로 포함하는 가능한 한 가장 짧은 문자열을 보낸다. 이렇게 하면 전송된 문자열을 보는 원치 않는 당사자들이 $s$가 아니라 미끼 $d$만 알아차리기를 기대하는 것이다. Boschua의 끔찍한 암호화 방식을 실행하기 위해 $s$와 $d$의 최단 공통 상위 수열을 구한다.

Boschua는 다음 문자열도 제공한다. 이는 $s$와 $d$ 모두의 부분 수열인 문자열 중 가장 긴 문자열이다. 그러한 문자열이 여러 개라면, 그중 임의의 하나가 주어진다. 이 문자열은 이전 프로젝트에서 남은 것이며 유용할 수도 있다고 한다.

채점

제출한 풀이는 각각 일정한 점수가 배정된 여러 테스트 그룹으로 평가된다. 각 테스트 그룹은 여러 테스트 케이스를 포함한다. 테스트 그룹의 점수를 얻으려면 해당 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$20$| $|s|,|d| \leq 1000$

$2$ |$70$| $|s|,|d| \leq 10^5$

$3$ |$10$| $|s|,|d| \leq 10^6$

입력의 첫 번째 줄에는 소문자 a-z로 이루어진 문자열 $s$이 주어진다.

입력의 두 번째 줄에는 소문자 a-z로 이루어진 문자열 $d$가 주어진다.

입력의 세 번째 줄에는 $s$와 $d$ 모두의 부분 수열인 문자열 중 가장 긴 문자열이 주어지며, 이 문자열은 소문자 a-z로 이루어져 있다.

두 $|s|, |d| \geq 1$임이 보장되지만, 최장 공통 부분 수열은 비어 있을 수도 있다.

$s$와 $d$가 모두 부분 수열로 나타나는 가장 짧은 문자열을 출력한다. 그러한 문자열이 여러 개라면 아무거나 출력해도 된다.

예제 $1$에서는 $s$와 $d$에 공통 문자가 없으므로, 모든 답은 두 문자열을 모두 온전히 포함해야 한다.

예제 $2$에서는 $s$와 $d$가 모두 adbadc의 부분 수열이다. 먼저, abac은 다음과 같이 얻을 수 있다: **a**d**ba**d**c**. 마찬가지로, adbdc도 다음과 같이 얻을 수 있다: **adb**a**dc**.