비밀번호

Johnny는 컴퓨터 보안에 집착한다. 웹사이트마다 다른 비밀번호를 쓰고, 출력한 종이도 파쇄한다. 그런데 이런 사고가 났다. 비밀번호가 적힌 종이를 실수로 분쇄기에 넣어버린 것이다. 그런데 놀랍게도, 이 종이는 각 조각이 텍스트의 한 열에 대응하도록 잘렸다. 게다가 Johnny는 모든 비밀번호가 영문 대문자로만 이루어져 있고, 서로 다르며, 길이가 모두 같고, 사전순으로 적혀 있었다는 사실을 확실히 알고 있다. Johnny는 열에 번호를 붙여 나란히 놓았지만, 자신이 정한 순서가 올바른지 확신하지 못한다. Johnny를 도와 각 행에 적힌 단어들이 사전순으로 정렬되도록 텍스트의 열을 순열로 재배열하는 방법을 계산하는 프로그램을 작성하시오. 가능한 순열이 여러 개라면 그중 사전순으로 가장 작은 것을 선택한다.

첫째 줄에 두 자연수 $n, m$ ($1 \le n \cdot m \leq 10^6$)이 공백으로 구분되어 주어진다. 다음 $n$개 줄에 $n$개의 단어가 한 줄에 하나씩 주어진다. 각 단어는 영문 대문자 $m$개로 이루어진다.

각 행의 단어들이 사전순으로 정렬되도록 하는 열의 순열을 나타내는 $m$개의 자연수를 한 줄에 출력한다. 그러한 순열이 여러 개라면 그중 사전순으로 가장 작은 것을 출력한다. 그러한 순열이 없으면 대신 "NIE" (폴란드어로 '아니오')를 출력한다.

예제 1에서 설명한 방식으로 열을 재배열하면 단어 "MTOEK", "SKAIA"를 얻으며, 이들은 사전순으로 정렬되어 있다.

예제 2에서는 열을 어떻게 재배열해도 각 행에서 얻어지는 단어들이 사전순으로 정렬되게 할 수 없다.