Igra

시간 제한1초메모리 제한64 MB

요약

길이 N인 두 문자열이 주어질 때, 두 번째 문자열의 글자를 재배열해 첫 번째와 같은 위치에서 겹치지 않으면서 사전순으로 가장 작은 문자열을 만든다.

난이도: 보통10점 중 6점
유형: 그리디, 문자열, 조합론
정답자: 아직 제출이 없습니다

문제

미르코와 슬라브코는 스키 여행이 지루해서 게임을 하나 만들었다. 먼저 미르코가 수 $N$ 을 정한다. 그러면 슬라브코는 단어를 만들 때 쓸 문자 $N$ 개를 적는다. 이어서 미르코가 길이 $N$ 의 단어를 적는다. 슬라브코는 자기가 고른 문자를 하나도 남기지 않고 모두 써서 단어를 만들어야 하는데, 어느 위치에서도 미르코의 단어와 같은 문자가 오면 안 된다. 게임을 더 팽팽하게 만들려고 슬라브코는 그런 단어 중 사전순으로 가장 앞선 것을 찾아야 한다. 이런 단어는 반드시 존재한다. 둘은 아직 어려서 a, b, c 세 문자만 알고, 이 점이 둘의 프로그래밍 실력에 큰 영향을 준다.

입력

첫째 줄에 양의 정수 $N$ 이 주어진다 ( $1 \le N \le 5000$ ).
둘째 줄에 슬라브코가 고른 문자를 나타내는 문자열이 주어진다. 길이는 $N$ 이고 소문자 a, b, c로만 이루어져 있다.
셋째 줄에 미르코가 적은 단어를 나타내는 문자열이 주어진다. 길이는 $N$ 이고 소문자 a, b, c로만 이루어져 있다.
조건을 만족하는 단어가 하나 이상 존재하는 입력만 주어진다.

전체 40점에 해당하는 테스트 케이스에서는 $1 \le N \le 20$ 이다.

출력

슬라브코가 찾은 단어를 첫째 줄에 출력한다.

예제3

예제 1
입력
```
3
abc
abc
```
예상 출력
```
bca
```
예제 2
입력
```
4
baba
baab
```
예상 출력
```
abba
```
예제 3
입력
```
5
aaabc
abcba
```
예상 출력
```
baaac
```