Mikhail postanowił nauczyć się grać w uogólnione szachy. W tym celu przygotował szachownicę o rozmiarze $n \times n$ pól. Każde pole na przecięciu wiersza $i$ i kolumny $j$ jest pokolorowane kolorem $a_{ij}$.
Mikhail jest początkującym graczem i mógł pokolorować szachownicę nieprawidłowo. Dlatego niektóre pola na szachownicy mogą wymagać przemalowania. Szachownica jest uważana za poprawnie pokolorowaną, jeśli spełnione są dwa warunki:
- Pola na szachownicy są pokolorowane co najwyżej dwoma różnymi kolorami.
- Nie ma sąsiednich pól (stykających się bokiem) pokolorowanych tym samym kolorem.
Mikhail zdał sobie sprawę, że gra na dużej szachownicy byłaby dla niego zbyt trudna. Dlatego może wyciąć ze swojej szachownicy mniejszą, pozostawiając prostokątny obszar składający się z pierwszych $r$ wierszy i pierwszych $c$ kolumn, i pokolorować poprawnie tylko ten obszar. Dla każdej pary liczb $(r, c)$, gdzie $1 \le r \le n$ i $1 \le c \le n$, oblicz wartość $b_{rc}$ – minimalną liczbę pól, które należy przemalować, aby prostokątny obszar pierwszych $r$ wierszy i pierwszych $c$ kolumn był poprawnie pokolorowany.
Wejście
Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 400$) – rozmiar szachownicy. Kolejnych $n$ wierszy opisuje szachownicę. $i$-ty z tych wierszy zawiera $n$ liczb całkowitych $a_{i1}, \dots, a_{in}$ ($1 \le a_{ij} \le 10^9$) – kolory pól w $i$-tym wierszu.
Wyjście
Wypisz $n$ wierszy, gdzie $i$-ty wiersz powinien zawierać $n$ liczb całkowitych $b_{i1}, \dots, b_{in}$.
Podzadania
| Podzadanie | Punkty | Dodatkowe ograniczenia | |
|---|---|---|---|
| 1 | 11 | $n \le 50$ | |
| 2 | 22 | $n \le 200$ | |
| 3 | 8 | $a_{ij} \le 2$ | |
| 4 | 17 | $a_{ij} \le 10$ | |
| 5 | 15 | $a_{ij} \le 100$ | |
| 6 | 7 | $a_{ij} \le 10^4$ | |
| 7 | 20 | - | |
Przykład
Wejście 1
2 7 7 7 7
Wyjście 1
0 1 1 2
Wejście 2
3 1 1 2 2 4 4 3 1 2
Wyjście 2
0 1 1 0 2 4 1 3 5