받아쓰기

면접 대비

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

요약
길이가 N인 세 답안 문자열이 주어질 때, 첫 번째가 두 번째보다, 두 번째가 세 번째보다 점수가 엄격히 높아지도록 정답 문자열을 만들거나 불가능하면 -1을 출력한다.
난이도

보통10점 중 6점

유형
그리디, 문자열, 구현, 수학
정답자
아직 제출이 없습니다

문제

오늘은 숭고한 초등학교의 받아쓰기 시험 날이다. 받아쓰기 시험의 정답은 길이가 NN인 문자열 SS이다. 정답 문자열 SS는 영어 알파벳 소문자로만 이루어져 있다.

초등학생 숭돌이, 고돌이, 한돌이는 각각 받아쓰기 시험 답안으로 문자열 S_S,S_K,S_HS\_S, S\_K, S\_H를 제출했다. 답안 문자열 S_S,S_K,S_HS\_S, S\_K, S\_H는 모두 길이가 NN이며, 영어 알파벳 소문자로만 이루어져 있다.

선생님은 답안 S_S,S_K,S_HS\_S, S\_K, S\_H를 정답 SS와 비교해서 순위를 매겼다. 구체적으로는 다음과 같다.

  • 1≤i≤N1 \leq i \leq N인 모든 ii에 대하여, 답안의 ii번째 문자가 정답의 ii번째 문자와 같다면 점수를 11점씩 얻는다.
  • 점수가 가장 높은 답안이 11위, 두 번째로 높은 답안이 22위, 세 번째로 높은 답안이 33위가 된다.

숭돌이가 11위, 고돌이가 22위, 한돌이가 33위일 때, 가능한 정답 문자열 SS를 구하여라. 가능한 정답 문자열이 하나도 존재하지 않는다면, -1을 출력하라.

단, 숭돌이와 고돌이와 한돌이 중 동점이 존재하는 경우는 정답으로 인정되지 않음에 유의하라.

입력

첫째 줄에 문자열의 길이 NN이 주어진다. (1≤N≤200,000)(1 \leq N \leq 200\\,000)

둘째 줄에 숭돌이의 답안을 나타내는 길이 NN의 문자열 S_SS\_S가 주어진다.

셋째 줄에 고돌이의 답안을 나타내는 길이 NN의 문자열 S_KS\_K가 주어진다.

넷째 줄에 한돌이의 답안을 나타내는 길이 NN의 문자열 S_HS\_H가 주어진다.

모든 답안은 영어 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 가능한 정답 문자열을 출력한다. 정답 문자열은 길이가 NN이며, 영어 알파벳 소문자로만 이루어져 있어야 한다. 가능한 답이 여러 가지라면, 그중 아무것이나 출력한다.

가능한 정답 문자열이 존재하지 않는다면, -1을 대신 출력한다.

예제2

  1. 예제 1

    입력
    5
    abcde
    efgtb
    abgte
    
    예상 출력
    efcde
    
  2. 예제 2

    입력
    5
    aaaaa
    aaaab
    aaaac
    
    예상 출력
    -1