W najbliższym odcinku Gry o Fotel kręcona będzie wielka bitwa pomiędzy wojskami Północy i Królewskiego Portu.

Scenarzyści postanowili w niej wprowadzić nowy rodzaj broni - czterokrotne działo, potrafiące strzelać jednocześnie w 4 strony świata. Pole bitwy jest oczywiście nieregularnym terenem (pagórki, doliny, woda, wysokie trawy...), dlatego czasami do utrzymania działa, w konkretnym miejscu potrzeba więcej żołnierzy.

Tym razem nie tylko twórcy serialu mają pełne ręce roboty, ponieważ podczas opracowywania scenariuszy starć potrzebna jest pomoc wybitnych strategów.

Ich zadaniem jest rozmieszczenie nowych dział na podanym polu bitwy w taki sposób, by nie mogły one strzelać do siebie nawzajem (to znaczy, że dwa działa nie mogą się znaleźć w tej samej kolumnie lub tym samym wierszu) oraz by w sumie liczba żołnierzy potrzebnych do utrzymania wszystkich dział była jak najmniejsza.
Wejście:

Na wejściu program otrzyma liczbę dodatnią 1<=n<=35, oznaczającą rozmiar kwadratowego pola bitwy, na którym należy rozmieścić n dział. W kolejnych n wierszach znajdzie sią ciąg n liczb naturalnych, odnoszących się do pojedynczego obszaru, na którym można ustawić działo, gdzie każda liczba będzie oznaczała liczbę żołnierzy, potrzebnych do utrzymania działa na danym polu.

Wyjście:

Na wyjściu program musi wypisać n liczb oznaczających numer rzędu, w którym należy ustawić działo dla każdej kolumny. Wyświetlone rozwiązanie musi być pierwsze w porządku leksykograficznym.

Przykład
Wejście:
4
5 3 2 2
1 2 3 3
2 1 8 7
3 5 3 2

Wyjście:
1 2 0 3