시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB115987976178.860%

문제

모르고리즘 회장 태윤이는 2024년 모르고리즘을 이끌어갈 회장을 고르려고 한다. 태윤이가 회장을 직접 고르는 이유는 아무도 회장을 맡고 싶어 하지 않기 때문이다. 따라서 태윤이는 이름이 세 글자인 사람 중에서, 사전 순으로 가장 앞선 사람을 회장으로 뽑으려고 한다.

사람들의 이름은 모두 서로 다르고, 길이가 $2$ 이상 $5$ 이하인 알파벳 대문자 A - Z로 이루어져 있다.

이름 $S$가 이름 $T$에 비해 사전 순으로 앞선다는 것은 아래 두 조건 중 하나가 성립하는 것과 동치이다. 이때 $\lvert S \rvert$는 $S$의 길이이고, $S[i]$는 $S$의 $i$번째 문자를 의미한다.

  • $S$가 $T$의 접두사이다. 즉, $\lvert S \rvert < \lvert T \rvert$이고, 모든 $1 \leq i \leq \lvert S \rvert$에 대해 $S[i] = T[i]$이다.
  • 처음으로 $S[i] \neq T[i]$인 $i$에 대해 $S[i] < T[i]$이다. ($1 \leq i \leq \min(\lvert S \rvert, \lvert T \rvert)$)

어떤 사람이 회장으로 선정될지 결과를 예측해 보자.

입력

입력은 다음과 같이 주어진다.

$N$

$name_1$

$name_2$

$\cdots$

$name_{N-1}$

$name_N$

첫째 줄에 사람의 수 $N$이 주어진다.

이어 $N$줄에 걸쳐 사람들의 이름 $name_i$가 주어진다.

출력

회장으로 뽑힐 사람을 출력한다.

제한

  • $1 \leq N \leq 100\,000$
  • $2 \leq \lvert name_i \rvert \leq 5$
  • 이름이 세 글자인 사람은 반드시 존재한다.
  • 각 이름은 최대 한 번만 주어진다.

예제 입력 1

7
KGW
LH
AHC
LKY
DREAM
AA
KTY

예제 출력 1

AHC

이름이 세 글자인 사람은 KGW, AHC, LKY, KTY이다. 이 중 사전 순으로 가장 앞선 AHC를 출력한다.