비밀번호 편집증

요원 August에게 당신의 도움이 필요한 문제가 있다. August는 동료 요원들과 소통할 때 사용하는 이메일 주소가 두 개 있다. 하지만 그는 얼마 전부터 어떤 정체불명의 사람이 자신이 누르는 모든 키를 감시하고 있다고 의심한다. 무엇보다도 이제 이 사람은 August가 두 이메일 주소에 사용하는 비밀번호 두 개를 알고 있다.

두 비밀번호 $s_1$와 $s_2$는 문자 a`''-z`''로 이루어진 문자열이다. 두 비밀번호는 최대 길이가 각각 $l_1$와 $l_2$인 서로 다른 두 텍스트 상자에 입력된다. 텍스트 상자의 최대 길이는 그 텍스트 상자에 들어갈 수 있는 글자 수를 결정하는 양의 정수이다. 문자 키를 누르면 해당 문자가 텍스트 상자의 맨 뒤에 들어간다. 단, 텍스트 상자에 들어 있는 글자 수가 최대 길이와 같으면 아무 일도 일어나지 않는다.

혼란을 일으키기 위해 August는 첫 번째 텍스트 상자에 $s_1$가 들어가고 두 번째 텍스트 상자에 $s_2$가 들어가도록 하는 키 입력 순서를 원한다. 그러면 정체불명의 감시자는 August가 어느 이메일 주소를 사용하는지 알 수 없다. 당신의 과제는 그러한 순서를 구성하는 것이다. 사용할 수 있는 키는 $27$개이며, 문자 a`''-z''와 ```<'' (backspace)이다. 백스페이스를 누르면 상자의 마지막 문자가 사라진다(상자에 글자가 적어도 하나 있을 때이며, 그렇지 않으면 아무 일도 일어나지 않는다).

만점을 받으려면 가능한 한 적은 문자를 포함하는 순서를 찾아야 한다. 일부 테스트 그룹에서는 문자가 최대 $10^6$개인 순서만 찾으면 된다.

채점

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$7$| 비밀번호는 문자 ```a`''로만 이루어져 있으며, $K = 0$이다.

$2$ |$30$| $K = 0$.

$3$ |$11$| 비밀번호는 문자 a`''와 b`''로만 이루어져 있으며, $l_1, l_2 \leq 5$이다.

$4$ |$15$| $l_1, l_2 \leq 50$.

$5$ |$17$| $l_1, l_2 \leq 200$.

$6$ |$20$| 추가 제한이 없다.

첫째 줄에 최단 해를 찾아야 하는지를 나타내는 정수 $K \in \{0, 1\}$가 주어진다. $K = 1$이면 최단 해를 찾아야 하며, 그렇지 않으면 문자가 최대 $10^6$개인 해면 충분하다.

첫째 줄에 문자열 $s_1$와 정수 $l_1$가 주어진다 ($1 \leq |s_1| \leq l_1 \leq 1000$).

둘째 줄에 문자열 $s_2$와 정수 $l_2$가 주어진다 ($1 \leq |s_2| \leq l_2 \leq 1000$).

$s_1$와 $s_2$는 모두 a`''부터 z`''까지의 소문자만 포함한다.

문제에서 설명한 키 입력 순서가 존재하지 않으면 느낌표 ```!`''를 출력한다.

그렇지 않으면 문자 a`''-z''와 ```<''로 이루어진 문자열, 즉 찾은 순서를 출력한다. 해가 여러 개라면 그중 아무거나 출력할 수 있다. $K = 1$이면 순서는 가능한 한 짧아야 하며, 그렇지 않으면 문자가 최대 $10^6$개이면 충분하다. 해가 존재한다면 문자가 최대 $10^6$개인 해가 존재함이 보장된다.

첫 번째 문자 <`''를 누를 때는 상자들에 아무것도 들어 있지 않으므로 아무 일도 일어나지 않는다. 이어지는 네 번의 키 입력 후에는 원하는 대로 두 번째 상자에 bara''가 들어 있지만, 첫 번째 상자의 최대 길이는 $3$이므로 그 상자에는 ```bar''가 들어 있다. 그다음 마지막 문자 두 개가 삭제되어 첫 번째 상자에는 ``b''가, 두 번째 상자에는 ba`''가 들어 있게 된다. 마지막으로 ra''를 입력하여 ```bra''와 ```bara`''가 들어 있게 한다. 첫 번째 문자는 전혀 필요하지 않으므로 최단 순서로 해결할 수도 있었지만, $K = 0$이므로 상관없다는 점에 유의한다.