Ulice w Bajtomieście tworzą prostopadłą siatkę - prowadzą ze wschodu na
zachód lub z północy na południe.
Ulice północ-południe są ponumerowane od 1 do
w kolejności z zachodu na wschód.
Podobnie ulice wschód-zachód są ponumerowane od 1 do
w kolejności z południa na północ.
Każda ulica północ-południe przecina każdą ulicę wschód-zachód i odwrotnie,
każda ulica wschód-zachód przecina każdą północ-południe.
Odległość między dwiema sąsiednimi ulicami północ-południe, a także
sąsiednimi ulicami wschód-zachód jest równa jednemu kilometrowi.
W mieście znajduje się sklepów, a
każdy sklep jest położony przy skrzyżowaniu ulic.
Kupiec Bajtazar dostarcza towary do każdego z
sklepów, przy czym
część sklepów odwiedza kilka razy dziennie.
Bajtazar postanowił wybudować magazyn, z którego dostarczałby towary do
sklepów.
Magazyn powinien być położony przy skrzyżowaniu ulic.
Ciężarówka dostarczająca towary w trakcie jednego kursu może odwiedzić
tylko jeden sklep - wyjeżdża z magazynu, dostarcza towar do sklepu
i wraca do magazynu.
Ciężarówka zawsze jedzie najkrótszą trasą z magazynu do sklepu
i z powrotem.
Odległość między punktami
i
jest równa
Napisz program, który:
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą
(
), oznaczającą liczbę sklepów
w Bajtomieście.
Kolejne wierszy wejścia zawiera opisy sklepów.
Wiersz
-wszy zawiera trzy liczby całkowite
,
i
(
,
), oddzielone pojedynczymi odstępami.
Ten opis oznacza, że
-ty sklep jest położony na skrzyżowaniu
-tej ulicy północ-południe i
-tej ulicy wschód-zachód
i ciężarówka codziennie dojeżdża do tego sklepu
razy.
Pierwszy i jedyny wiersz wyjścia powinien zawierać dwie liczby całkowite
oraz
, oddzielone pojedynczym odstępem i opisujące położenie
magazynu jako skrzyżowanie
-tej ulicy północ-południe
i
-tej ulicy wschód-zachód.
Jeżeli istnieje wiele poprawnych wyników, Twój program powinien
wypisać dowolny z nich.
3 2 2 1 6 2 1 4 6 1poprawną odpowiedzią jest:
4 4
Poniższy rysunek przedstawia sytuację z przykładowego wejścia. Ponumerowane punkty oznaczają odpowiednie sklepy. Punkt S oznacza optymalne położenie magazynu.