Distància màxima P99716

Statement

Considereu un món bidimensional. La distància Manhattan entre dues posicions $(i_1, j_1)$ i $(i_2, j_2)$ es defineix com $\vert i_1 - i_2 \vert + \vert j_1 - j_2 \vert$ . Per exemple, la distància entre $(7, 3)$ i $(2, 9)$ és $\vert 7 - 2 \vert + \vert 3 - 9 \vert = 5 + 6 = 11$ .

Donada una matriu $M$ amb $n$ files i $m$ columnes, trobeu la màxima distància Manhattan entre tots els parells de posicions $(a, b)$ i $(c, d)$ tals que @M[a][b]@ $\ne$ @M[c][d]@.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$ i $m$ , seguides de la matriu en $n$ línies, cadascuna amb $m$ enters. La matriu té entre 2 i $10^5$ valors entre 1 i $10^9$ .

Sortida

Per a cada matriu, escriviu la màxima distància Manhattan entre tots els parells de posicions amb valors diferents. Cada matriu tindrà almenys dos valors diferents.

Public test cases

Input

1 2
1000 2000

3 1
1000000000
999999999
999999998

2 5
42 42 42 42 42
42 42 10 23 42

Output

1
2
4

Information

Author: Izan Beltrán
Language: Catalan
Official solutions: C++ Python
User solutions: C++