한 지역 ICPC 대회의 위원회는 적절한 대회 환경을 제공하지 못하게 되자, 팀들의 순위를 사전식 순서(lexicographical order)로 결정하기로 했습니다. 즉, 팀 이름이 사전식으로 가장 앞서는 팀이 우승하게 됩니다.
이 문제의 주인공인 에트나는 어떤 팀의 팀장입니다. 팀의 정체는 밝히지 않겠지만, 그 팀의 이름이 'Z'로 시작하여 매우 불리한 상황에 처해 있다는 점만은 말해두겠습니다. 위원회와 긴 논의 끝에, 에트나는 조금 더 공정한 순위 결정 방식을 얻어냈습니다. 안타깝게도 팀들은 여전히 사전식 순서로 정렬되지만, 사전식 순서의 정의가 변경됩니다. 더 정확히 말하면, 위원회는 영어 알파벳의 순열을 무작위로 선택하고, 그 순열을 사용하여 사전식 순서를 자연스럽게 정의합니다. 즉, 순열에서의 알파벳 순서가 곧 사전식 순서가 됩니다.
에트나는 즉시 노트북을 꺼내 각 팀에 대해 그 팀이 우승할 수 있는 알파벳 순열을 찾는 프로그램을 작성했습니다. 안타깝게도 그 프로그램은 아직까지도 실행이 끝나지 않았습니다. 에트나를 도와 같은 기능을 수행하는 더 효율적인 프로그램을 작성해 주세요.
입력
첫 번째 줄에는 대회에 참가하는 팀의 수 $N$이 주어집니다. 이어지는 $N$개의 줄에는 대회에 참가하는 팀의 이름이 주어집니다. 각 팀의 이름은 소문자 영어 알파벳으로만 구성된 한 단어입니다. 물론, 팀 이름들은 서로 다릅니다.
출력
입력에 주어진 순서대로 각 팀에 대해, 해당 팀이 우승할 수 있는 영어 알파벳 순열을 한 줄에 하나씩 출력합니다. 만약 그러한 순열이 존재하지 않는다면 "nemoguce"를 출력하며, 그러한 순열이 여러 개 존재한다면 아무거나 하나를 출력하면 됩니다.
서브태스크
$L$을 모든 $N$개 팀 이름 길이의 합이라 하고, $K$를 모든 팀 이름에 등장하는 서로 다른 알파벳의 개수라고 합니다.
| 서브태스크 | 점수 | 제한 |
|---|---|---|
| 1 | 13 | $1 \le N \le 100, 1 \le L \le 10\,000, 1 \le K \le 6$ |
| 2 | 32 | $1 \le N \le 350, 1 \le L \le 10\,000, 1 \le K \le 26$ |
| 3 | 55 | $1 \le N \le 25\,000, 1 \le L \le 1\,000\,000, 1 \le K \le 26$ |
예제
입력 1
3 war zag wro
출력 1
agorwzbcdefhijklmnpqstuvxy agorzwbcdefhijklmnpqstuvxy gorawzbcdefhijklmnpqstuvxy
입력 2
3 b ab aa
출력 2
bacdefghijklmnopqrstuvwxyz nemoguce abcdefghijklmnopqrstuvwxyz
입력 3
7 bcada dbaab bbabc ababb aacdf bcdff baddb
출력 3
cbadfeghijklmnopqrstuvwxyz cdabfeghijklmnopqrstuvwxyz bacdfeghijklmnopqrstuvwxyz nemoguce abcdfeghijklmnopqrstuvwxyz cbdafeghijklmnopqrstuvwxyz nemoguce