Firma kapitana Mambeksa zajmuje się dystrybucją napoi. W każdym mieście do którego kapitan dostarcza napoje trzeba wyznaczyć położenie magazynu z napojami. Suma odległości magazynu z napojami od lokali serwujących napoje powinna być jak najmniejsza. Ponieważ miasta do których kapitan dostarcza napoje są bardzo gęsto zabudowane, rzeczywisty czas potrzebny na pokonanie drogi między dwoma punktami wyznacza tzw. metryka miejska. Odległość dwóch punktów P1(x1, y1) i P2(x2, y2) w metryce miejskiej jest określona następującym wzorem:
d(P1, P2) = |x1 - x2| + |y1 - y2|
Napisz program który pomoże kapitanowi wyznaczyć optymalne położenie magazynów w miastach.
W pierwszym wierszu zapisana jest liczba zestawów danych wejściowych n (n ≥ 0 i n ≤ 20). W kolejnych wierszach jest zapisanych n zestawów danych wejściowych. W każdym zestawie testowym jest opisane położenie lokali w jednym mieście. W pierwszym wierszu znajduje się liczba lokali m (m ≥ 0 i m ≤ 2500). W kolejnych m wierszach są zapisane pary liczb x, y oddzielone odstępem (x ≥ 0, x ≤ 10000, y ≥ 0 i y ≤ 10000 ) - są to współrzędne lokali w mieście.
Dla każdego zestawu danych wejściowych program ma wypisać jeden wiersz zawierający odległości magazynu od lokali w danym mieście.
3 4 0 0 3 0 3 1 2 2 3 1 1 5 2 3 3 3 6 6 2 2 4 4
7 6 8