Codah ClubΕξασκήσου. Υπόβαλε. Βελτιώσου.
Σύνδεση
Ελληνικά
#00064F

Ključ - Državno

The Secret Committee has worked hard preparing the tasks for this year's Nationals, and the time has come to send those tasks to the places where the competition will be held. Of course, the tasks are kept as top secret, so they are ecrypted with a well known algorithm in the Secret Committee's labs prior to being sent.


The described algorithm encrypts a text of length N ∙ M in the following manner: a matrix containing N rows and M columns gets filled with letters from the text line by line, downwards. Afterwards, some columns' places are swapped. Formally, the key used for the encryption is a permutation of numbers from 1 to M. We represent the key as a sequence (a1, a2 ,... , aM), where ai represents the new position of the ith column in the matrix. After applying the key, the encrypted text is read from the matrix in the same order as it was added to the matrix.


Unfortunately, the Committee members are suffering from slight amnesia and they can't recall the key they used for the encryption. Of course, since the Secret Committee is very responsible, a plan was already devised in the event that this happens. In a secret safe, stored in the Secret Committee HQ (the location of which is also secret), they have stored a text with a very important quality - by encrypting that text with any key, no lexicographically greater encrypted text is got than the one encrypted using the forgotten key.


You are given the matrix to be encrypted. Determine the forgotten key.


InputFrom the first line of the standard input read two integers N and M (1 ≤ N, M ≤ 2.000), the number of rows and columns of the matrix to be encrypted, respectively. In the following N lines there are M lowercase letters of the english alphabet in each, representing the matrix to be encrypted.

OutputIn the first and only line of the standard output write M numbers separated by a space, which represent the key used to encrypt the given matrix. The solution will be unique.

Input:
4 3
kom
isi
jar
ulz
Output:
3 1 2
Explanation: By applying the key 3 1 2, the first column is moved to the third column's space, the second column is moved to the first, and the third is moved to the second. By reading from the encrypted matrix we get the text omksiiarjlzu. If we apply any other key we will get a lexicographically smaller encrypted text.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.