고대 돌판 해독
시간 제한2초메모리 제한128 MB
각 행과 각 열에서 한 칸씩 선택해 고른 글자를 오름차순으로 정렬했을 때 사전 순으로 가장 앞에 오도록 출력합니다.
문제
Y 교수는 고대 유물을 발굴한다. 최근에 찾아낸 돌판에는 글자 개가 격자로 새겨져 있고, 돌판 한 장은 길이 인 메시지 하나를 담고 있다. 돌판을 읽는 절차는 다음과 같다.
- 격자에서 글자 개를 고른다. 고른 글자 중 어느 두 개도 같은 행에 있으면 안 되고 같은 열에 있어서도 안 된다.
- 고른 글자를 원하는 순서로 이어 붙여 길이 인 문자열을 만든다.
- 2번에서 만들 수 있는 문자열 중 사전순으로 가장 앞선 것이 이 돌판의 메시지다.
글자의 크기 순서는 ASCII 값 순서와 같다. 즉 이다.
돌판 한 장이 주어지면 그 돌판의 메시지를 구하라.
입력
입력 형식은 다음과 같다.
N
c11c12...c1N
c21c22...c2N
:
:
cN1cN2...cNN
첫 줄에 정수 ()이 주어진다. 이어지는 개 줄에는 각각 길이 인 문자열이 주어진다. 문자열의 각 글자는 영어 대문자 또는 소문자다 (A-Z, a-z).
출력
돌판의 메시지를 한 줄에 출력한다.