Tajna Komisija vredno je radila na pripremi zadataka za Državno takmičenje i došlo je vreme da se zadaci pošalju na mesta održavanja takmičenja. Naravno, zadaci se čuvaju kao stroga tajna, pa se pre slanja šifruju dobro poznatim algoritmom nastalim u laboratorijama Tajne Komisije.

Algoritmom se šifruje tekst dužine N ∙ M na sledeći način: Matrica sa N redova i M kolona popunjava se slovima teksta red po red, odozgo na dole. Zatim se nekim kolonama u matrici zamene mesta. Formalno, ključ kojim se šifruje je jedna permutacija brojeva od 1 do M. Ključ predstavljamo nizom (a₁, a₂ ,... , a_M), gde a_i predstavlja novu poziciju i-te kolone u matrici. Nakon primene ključa, šifrat (šifrovani tekst) se čita iz matrice istim redosledom kojim je originalni tekst unet u matricu.

Međutim, članovi komisije su malo zaboravni i ne sećaju se ključa koji koriste za šifrovanje zadataka. Naravno, kako je Tajna Komisija veoma odgovorna, ranije je izrađen plan i za ovu situaciju. U tajnom sefu, koji se nalazi negde u zgradi Tajne Komisije (čija lokacija je takođe tajna), sačuvali su jedan tekst sa veoma bitnom osobinom - šifrovanjem tog teksta bilo kojim kljušem ne dobija se leksikografski veći šifrat od šifrata dobijenim šifrovanjem pomoću zaboravljenog ključa.

Ako vam je poznata matrica koja se šifruje i činjenica da se njenim šifrovanjem dobija leksikografski najveći mogući šifrat, odredite ključ.

Ulaz.

(Ulazni podaci se učitavaju iz datoteke kljuc.in) U ulaznoj datoteci se u prvom redu nalaze dva broja N i M(1 ≤ N, M ≤ 2.000), broj redova i broj kolona matrice koja se šifruje, respektivno. U sledećih N redova nalazi se po M malih slova engleske abecede, koja predstavljaju matricu koja se šifruje.

Izlaz.

(Izlazni podaci se ispisuju u datoteku kljuc.out) U prvom i jedinom redu izlazne datoteke ispisati M brojeva razdvojenih razmakom, ključ kojim se šifruje matrica. Rešenje će biti jedinstveno.

Primer 1.

4 3
kom
isi
jar
ulz

3 1 2

Objašnjenje. Primenom ključa 3 1 2 prva kolona se premešta na treću, druga kolona se premešta na prvu, a treća kolona se premešta na drugu poziciju. Čitanjem iz šifrovane matrice dobija se tekst omksiiarjlzu. Primenom bilo kog drugog ključa dobija se leksikografski manji šifrat.

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int kMaxSize = 2001;

struct column  
{
    char characters[kMaxSize];
    int originalIdx;
};

char matrix[kMaxSize][kMaxSize];
column columns[kMaxSize];
int n, m;
int key[kMaxSize];

bool cmp(const column& first, const column& second)
{
    return strcmp(first.characters, second.characters) > 0;   
}

int main()
{
    freopen("kljuc.in", "r", stdin);
    freopen("kljuc.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", matrix[i]);   
    }
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            columns[i].characters[j] = matrix[j][i];   
        }   
        columns[i].characters[n] = 0;
        columns[i].originalIdx = i;
    }    
    sort(columns, columns + m, cmp);
    for (int i = 0; i < m; i++)
    {
        key[columns[i].originalIdx] = i + 1;   
    }
    for (int i = 0; i < m; i++)
    {
        printf("%d ", key[i]);   
    }
    return 0;
}

const
  MaxN = 2012;

var
        inFile, outFile : text;
  n, m, i, j: longint;
  s : array[0..MaxN, 0..MaxN] of char;
  ind, sol : array[0..MaxN] of longint;

function less(a, b : longint) : boolean;
var
  i : longint;
  q : boolean;
begin
        q := false;
  for i := 1 to n do
  begin
    if (s[a][i] > s[b][i]) then q := true;
    if (s[a][i] < s[b][i]) then q := false;
    if (s[a][i] <> s[b][i]) then break;
  end;

  less := q;
end;

procedure QS(l, r : longint);
var
        i , j, mid, x, tmp2 : longint;
        tmp : char;
begin
  i := l; j := r;
        mid := (l + r) div 2;
        for x := 1 to n do s[m + 1][x] := s[mid][x];
        repeat
    while (less(i, m + 1)) do i := i + 1;
    while (less(m + 1, j)) do j := j - 1;
    if (i <= j) then
    begin
      for x := 1 to n do
      begin
        tmp := s[i][x]; s[i][x] := s[j][x]; s[j][x] := tmp;
      end;
      tmp2 := ind[i]; ind[i] := ind[j]; ind[j] := tmp2;
                        i := i + 1; j := j - 1;
    end;
  until (i > j);

  if (l < j) then QS(l, j);
  if (i < r) then QS(i, r);
end;

BEGIN

  assign(inFile, 'kljuc.in');
  assign(outFile, 'kljuc.out');
  reset(inFile); rewrite(outFile);

  readln(inFile, n, m);
  for i := 1 to n do
  begin
    for j := 1 to m do
      read(inFile, s[j][i]);
    readln(inFile);
  end;

  for i := 1 to m do
    ind[i] := i;
  QS(1, m);
  for i := 1 to m do
    sol[ ind[i] ] := i;

  for i := 1 to m - 1 do
    write(outFile, sol[i], ' ');
  writeln(outFile, sol[m]);

  close(inFile);
  close(outFile);

END.