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