시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 145 29 11 18.644%

문제

구사과와 큐브러버는 공동 창업을 하려고 한다. 두 사람은 회사 이름을 아직 결정하지 못했고, 서로가 생각한 회사 이름이 상대방을 설득하지 못해 일을 시작하지 못하고 있었다. 더 이상 일정을 늦출 수 없는 두 사람은 게임을 통해 회사 이름을 정하기로 했다. 다행히도 두 사람은 회사 이름의 길이에 대한 의견이 일치하고, N개의 글자로 이루어져 있어야 한다.

두 사람은 각자 사용할 N개의 문자를 정했다. 같은 문자가 여러 번 포함되었을 수도 있다. 가장 처음에 회사의 이름은 물음표(?) N개이다. 이제, 서로 턴을 번갈아 가지면서 게임을 진행하려고 한다. 게임은 구사과가 먼저 시작한다.

각 턴이 되었을 때, 각 사람은 미리 정해놓은 문자 중 하나를 고르고, 물음표 하나를 고른 문자로 변경한다. 고른 문자는 더 이상 사용할 수 없다. 게임은 모든 물음표가 문자로 바뀌면 끝난다.

예를 들어, 정보를 좋아하는 구사과가 고른 문자가 [i, o, i] 이고, 수학을 좋아하는 큐브러버가 고른 문자가 [i, m, o]인 경우가 있다면, 게임은 다음과 같이 진행될 수 있다.

  • 가장 처음에 회사 이름은 ???이다.
  • 구사과가 두 번째 물음표를 i로 변경해 회사 이름을 ?i?로 변경한다. 이제 구사과의 고른 문자는 [i, o] 이다.
  • 큐브러버가 세 번째 물음표를 o로 변경해 회사 이름을 ?io로 변경한다. 이제 큐브러버의 고른 문자는 [i, m] 이다.
  • 마지막으로, 구사과가 첫 번째 물음표를 o로 변경해 회사 이름을 oio로 변경한다.
  • 최종적으로 회사의 이름은 oio가 된다.

구사과는 회사 이름을 사전 순으로 가장 앞서게 만들고 싶어하고, 큐브러버는 회사 이름을 사전 순으로 가장 뒤에 오게 만들고 싶어한다.

두 사람이 게임을 최적의 방법으로 진행했을 때, 회사 이름이 무엇인지 알아내는 프로그램을 작성하시오.

입력

입력은 길이가 N(1 ≤ N ≤ 300,000)인 문자열 두 개로 이루어져 있다. 모든 문자열은 알파벳 소문자로만 이루어져 있다. 첫 번째 줄에 주어지는 문자열은 구사과가 고른 문자이고, 두 번째 줄에 주어지는 문자열은 큐브러버가 고른 문자이다.

출력

두 사람이 창업한 회사의 이름을 출력한다.

예제 입력 1

ioi
imo

예제 출력 1

ioi

예제 입력 2

koooosaga
cubelover

예제 출력 2

avaugrkoo

예제 입력 3

cubehater
cubelover

예제 출력 3

avbucreoe

예제 입력 4

startlink
startlink

예제 출력 4

atitkslrn

출처