Mikhaïl a décidé d'apprendre à jouer aux échecs généralisés. Pour cela, il a préparé un échiquier de taille $n \times n$ cases. Chaque case à l'intersection de la ligne $i$ et de la colonne $j$ est colorée avec la couleur $a_{ij}$.
Mikhaïl est un joueur débutant et a peut-être mal coloré le plateau. Par conséquent, certaines cases du plateau peuvent nécessiter d'être repeintes. Le plateau est considéré comme correctement coloré si deux conditions sont remplies :
- Les cases du plateau sont colorées avec au plus deux couleurs distinctes.
- Il n'y a pas de cases adjacentes (partageant un côté) colorées avec la même couleur.
Mikhaïl s'est rendu compte que jouer sur un grand plateau serait trop difficile pour lui. Par conséquent, il pourrait découper un plateau plus petit de son plateau, en laissant une zone rectangulaire constituée des $r$ premières lignes et des $c$ premières colonnes, et colorer uniquement cette zone correctement. Pour chaque paire de nombres $(r, c)$ où $1 \le r \le n$ et $1 \le c \le n$, calculez la valeur $b_{rc}$ — le nombre minimal de cases à repeindre pour que la zone rectangulaire des $r$ premières lignes et des $c$ premières colonnes soit colorée correctement.
Entrée
La première ligne contient un entier $n$ ($1 \le n \le 400$) — la taille du plateau. Les $n$ lignes suivantes décrivent le plateau. La $i$-ème de ces lignes contient $n$ entiers $a_{i1}, \dots, a_{in}$ ($1 \le a_{ij} \le 10^9$) — les couleurs des cases de la $i$-ème ligne.
Sortie
Affichez $n$ lignes, où la $i$-ème ligne doit contenir $n$ entiers $b_{i1}, \dots, b_{in}$.
Sous-tâches
| Sous-tâche | Score | Contraintes supplémentaires | |
|---|---|---|---|
| 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 | - | |
Exemples
Entrée 1
2 7 7 7 7
Sortie 1
0 1 1 2
Entrée 2
3 1 1 2 2 4 4 3 1 2
Sortie 2
0 1 1 0 2 4 1 3 5