Mikhail decidió aprender a jugar ajedrez generalizado. Para ello, preparó un tablero de ajedrez de tamaño $n \times n$ casillas. Cada casilla en la intersección de la fila $i$ y la columna $j$ está coloreada con el color $a_{ij}$.
Mikhail es un jugador principiante y podría haber coloreado el tablero incorrectamente. Por lo tanto, es posible que sea necesario repintar algunas casillas del tablero. El tablero se considera correctamente coloreado si se cumplen dos condiciones:
- Las casillas del tablero están coloreadas con no más de dos colores distintos.
- No hay casillas adyacentes (que compartan un lado) coloreadas con el mismo color.
Mikhail se dio cuenta de que jugar en un tablero grande sería demasiado difícil para él. Por lo tanto, podría recortar un tablero más pequeño de su tablero, dejando un área rectangular que consiste en las primeras $r$ filas y las primeras $c$ columnas, y colorear correctamente solo esta área. Para cada par de números $(r, c)$ donde $1 \le r \le n$ y $1 \le c \le n$, calcula el valor $b_{rc}$: la cantidad mínima de casillas que deben ser repintadas para que el área rectangular de las primeras $r$ filas y las primeras $c$ columnas esté coloreada correctamente.
Entrada
La primera línea contiene un entero $n$ ($1 \le n \le 400$) — el tamaño del tablero. Las siguientes $n$ líneas describen el tablero. La $i$-ésima de estas líneas contiene $n$ enteros $a_{i1}, \dots, a_{in}$ ($1 \le a_{ij} \le 10^9$) — los colores de las casillas en la $i$-ésima fila.
Salida
Imprime $n$ líneas, donde la $i$-ésima línea debe contener $n$ enteros $b_{i1}, \dots, b_{in}$.
Subtareas
| Subtarea | Puntaje | Restricciones adicionales | |
|---|---|---|---|
| 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 | - | |
Ejemplos
Entrada 1
2 7 7 7 7
Salida 1
0 1 1 2
Entrada 2
3 1 1 2 2 4 4 3 1 2
Salida 2
0 1 1 0 2 4 1 3 5