아름다운 단어
시간 제한1초메모리 제한128 MB
한 명은 항상 맨 오른쪽 조각을 가져가고 다른 한 명은 최적으로 골라 사전순으로 가장 작은 단어를 만들 수 있는 게임을 시뮬레이션해서 승패를 비교합니다.
문제
상근과 희원은 한 줄로 놓인 종이 조각으로 단어를 만드는 게임을 한다. 각 종이에는 알파벳 소문자 하나가 적혀 있다. 두 사람은 번갈아 한 장씩 종이를 가져가고, 가져간 글자를 자신이 만들고 있는 단어의 뒤에 붙인다. 상근이 먼저 시작하며, 더 이상 종이가 없으면 게임이 끝난다.
두 단어를 비교했을 때 사전순으로 더 앞서는 단어를 더 아름다운 단어라고 한다. 두 사람이 만든 단어가 같으면 둘 다 이기지 못한다.
상근은 항상 남아 있는 종이 중 가장 오른쪽 종이를 가져간다. 희원은 이 사실을 알고 있으며, 자신의 차례에는 남아 있는 종이 중 아무 종이나 하나 가져갈 수 있다. 희원이 상근을 이길 수 있는지 판단하고, 희원이 만들 수 있는 가장 아름다운 단어를 구하시오.
입력
첫째 줄에 짝수 N이 주어진다. (2 <= N <= 100000)
둘째 줄에 처음 놓여 있는 종이의 글자를 왼쪽부터 오른쪽 순서대로 나타낸 길이 N의 문자열이 주어진다. 모든 글자는 알파벳 소문자이다.
출력
희원이 상근보다 사전순으로 더 앞서는 단어를 만들 수 있으면 첫째 줄에 DA를 출력하고, 그렇지 않으면 NE를 출력한다.
둘째 줄에는 희원이 만들 수 있는 가장 아름다운 단어를 출력한다.