Uolevilla on neliön muotoinen mustavalkokuva joka koostuu $n \times n$ pikselistä. Jokaisen pikselin väri on joku arvo väliltä $[0, 255255]$. $k \times k$ kokoisen neliön sotkuisuus on sen sisältämän suurimman ja pienimmän väriarvon erotus. Tehtävänäsi on laskea jokaiselle $1 \le k \le n$ kaikkien kuvan sisältämien $k \times k$ neliöiden sotkuisuuksien summa.

Syöte

Syötteen ensimmäisellä rivillä on yksi luku, $n$, kuvan korkeus ja leveys. Seuraavalla $n$ rivillä on jokaisella $n$ kokonaislukua, kuvan pikseleiden väriarvot.

Tuloste

Tulosta $k$ kokonaislukua, kaikkien $k \times k$ neliöiden sotkuisuuksien summa jokaiselle $1 \le k \le n$.

Rajat

• $1 \le n \le 400$

Tehtävässä haetaan $O(n^3)$ algoritmia.

Esimerkki

Syöte:

3
1 1 3
1 1 4
3 3 4

Tuloste:

0
8
3

Syöte:

4
5 2 3 3
2 2 1 3
2 2 4 4
5 1 3 3

Tuloste:

0
21
14
4